N students were giving an examination. The students were sitting in a line from 1 to N in order. The ith student had knowledge ki 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 kj > ki.There are M teachers who are the exam checkers - jth checker will check the answer-sheets of some continuosly sitting students from the index Li to Ri inclusive. All the students got this information before hand, so they decided that they won't copy the solutions from a person whose answer-sheet 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".
First line contains 2 space-separated positive integers - N and M - the total number of students and the number of exam checkers respectively.
Second line contains N space-separated integers, where the ith integer represents the knowledge of the ith student.
M lines follow - each line contains 2 space-separated integers - Lj and Rj, representing the continuous range of indexes whose answer sheet will be checked by the jth checker.
The (M + 3)th line contains a single integer D - the distance upto which each student can see for copying answers.
Print N lines, where ith line represents the answer for ith student.
On each line, print the knowledge of the student(s) from whom the ith 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).
1 ≤ N ≤ 10^5
1 ≤ M ≤ N
1 ≤ ki ≤ 10^8
1 ≤ Lj ≤ Rj ≤ N
1 ≤ D ≤ N
Subtask 1: 20 points
N ≤ 100
Subtask 2: 20 points
N ≤ 1000
Subtask 3: 60 points
No additional constraint
10 5 1 2 1 2 1 2 2 1 2 3 1 2 3 4 5 6 7 8 9 10 2
-1 -1 2 1 -1 2 2 -1 -1 3 1 -1 -1
|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|
Fetching successful submissions