Exam Copy

N students were giving an examination. The students were sitting in a line from 1 to N in order. The i^{th} student had knowledge k_{i} in the subject on which the exam was being conducted. Every student is not confident about his own preparation, so each student wants to find some students (possibly zero), from whom they can copy the answers. Student i can copy from student j only if k_{j} > k_{i}.There are M teachers who are the exam checkers  j^{th} checker will check the answersheets of some continuosly sitting students from the index L_{i} to R_{i} inclusive. All the students got this information before hand, so they decided that they won't copy the solutions from a person whose answersheet is being checked by the same checker as that of himself. Also, each student can see only up to distance D, so a student at index i, can copy solutions of students in the range i  D to i + D, both inclusive. From all the candidate students from which a student can copy, the student will copy from the most knowledgeable students.
For each student, print the knowledge of the student(s) from whom he can copy, as well as the number of such students.
If a certain student can not copy, print "1".
Input
First line contains 2 spaceseparated positive integers  N and M  the total number of students and the number of exam checkers respectively.
Second line contains N spaceseparated integers, where the i^{th} integer represents the knowledge of the i^{th} student.
M lines follow  each line contains 2 spaceseparated integers  L_{j} and R_{j}, representing the continuous range of indexes whose answer sheet will be checked by the j^{th} checker.
The (M + 3)^{th} line contains a single integer D  the distance upto which each student can see for copying answers.
Output
Print N lines, where i^{th} line represents the answer for i^{th} student.
On each line, print the knowledge of the student(s) from whom the i^{th} student can copy as per the rule mentioned in the statement, and the number of such students, separated by a space.
If the student can not copy from any student, print "1" (without the quotes).
Constraints
1 ≤ N ≤ 10^5
1 ≤ M ≤ N
1 ≤ k_{i} ≤ 10^8
1 ≤ L_{j} ≤ R_{j} ≤ N
1 ≤ D ≤ N
Subtasks
Subtask 1: 20 points
N ≤ 100
Subtask 2: 20 points
N ≤ 1000
Subtask 3: 60 points
No additional constraint
Example
Input
10 5 1 2 1 2 1 2 2 1 2 3 1 2 3 4 5 6 7 8 9 10 2
Output
1 1 2 1 1 2 2 1 1 3 1 1 1
Author:  wittyceaser 
Tags  wittyceaser 
Date Added:  23062016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions