The Eighth Wonder

Z tribe has been developing over time with buildings along the R river undergoing constant changes. Old buildings are demolished and replaced with new ones having different uniqueness values. Moreover, each member of the tribe has seen only a portion of these buildings and insists that the eighth most unique building they have personally witnessed is the true wonder.

The Z tribe leader is worried that differing opinions on which building is the eighth wonder might lead to discord. To address this, he has asked you to determine for each individual the uniqueness value of the building they consider the eighth wonder.

Given the initial list of buildings, a series of modification events that replace buildings with new ones, and several queries each specifying a range of buildings a person has seen, your task is to compute the eighth highest uniqueness value in each range. If the range contains fewer than 8 buildings, output -1.

inputFormat

The input is given as follows:

N Q
a1 a2 ... aN
M
pos1 new_value1
pos2 new_value2
... 
posM new_valueM
L1 R1
L2 R2
... 
LQ RQ

Here,

• N is the number of buildings along the R river.
• Q is the number of queries (people).
• The second line contains N integers representing the initial uniqueness values of the buildings in order.
• M is the number of modification events.
• Each of the next M lines contains two integers: pos (the 1-indexed position of the building to be replaced) and new_value (the uniqueness value of the new building).
• Each of the following Q lines contains two integers L and R (1-indexed) denoting the range of buildings that a person has seen.

outputFormat

For each query, output a single integer on a new line: the eighth highest uniqueness value among all buildings in the specified range after processing all modifications. If the range contains fewer than 8 buildings, output -1.

sample

10 2
10 20 30 40 50 60 70 80 90 100
2
5 95
2 85
1 10
3 7

40
-1