#D7325. Set Merging
Set Merging
Set Merging
You are given a permutation a_1, a_2, ..., a_n of numbers from 1 to n. Also, you have n sets S_1,S_2,..., S_n, where S_i=\{a_i}. Lastly, you have a variable cnt, representing the current number of sets. Initially, cnt = n.
We define two kinds of functions on sets:
f(S)=min_{u∈ S} u;
g(S)=max_{u∈ S} u.
You can obtain a new set by merging two sets A and B, if they satisfy g(A)<f(B) (Notice that the old sets do not disappear).
Formally, you can perform the following sequence of operations:
-
cnt← cnt+1;
-
S_{cnt}=S_u∪ S_v, you are free to choose u and v for which 1≤ u, v < cnt and which satisfy g(S_u)<f(S_v).
You are required to obtain some specific sets.
There are q requirements, each of which contains two integers l_i,r_i, which means that there must exist a set S_{k_i} (k_i is the ID of the set, you should determine it) which equals \{a_u∣ l_i≤ u≤ r_i}, which is, the set consisting of all a_i with indices between l_i and r_i.
In the end you must ensure that cnt≤ 2.2× 10^6. Note that you don't have to minimize cnt. It is guaranteed that a solution under given constraints exists.
Input
The first line contains two integers n,q (1≤ n ≤ 2^{12},1 ≤ q ≤ 2^{16}) — the length of the permutation and the number of needed sets correspondently.
The next line consists of n integers a_1,a_2,⋅⋅⋅, a_n (1≤ a_i≤ n, a_i are pairwise distinct) — given permutation.
i-th of the next q lines contains two integers l_i,r_i (1≤ l_i≤ r_i≤ n), describing a requirement of the i-th set.
Output
It is guaranteed that a solution under given constraints exists.
The first line should contain one integer cnt_E (n≤ cnt_E≤ 2.2× 10^6), representing the number of sets after all operations.
cnt_E-n lines must follow, each line should contain two integers u, v (1≤ u, v≤ cnt', where cnt' is the value of cnt before this operation), meaning that you choose S_u, S_v and perform a merging operation. In an operation, g(S_u)<f(S_v) must be satisfied.
The last line should contain q integers k_1,k_2,⋅⋅⋅,k_q (1≤ k_i≤ cnt_E), representing that set S_{k_i} is the ith required set.
Please notice the large amount of output.
Examples
Input
3 2 1 3 2 2 3 1 3
Output
6 3 2 1 3 5 2 4 6
Input
2 4 2 1 1 2 1 2 1 2 1 1
Output
5 2 1 2 1 2 1 5 3 3 1
Note
In the first sample:
We have S_1={1},S_2={3},S_3={2} initially.
In the first operation, because g(S_3)=2<f(S_2)=3, we can merge S_3,S_2 into S_4={2,3}.
In the second operation, because g(S_1)=1<f(S_3)=2, we can merge S_1,S_3 into S_5={1,2}.
In the third operation, because g(S_5)=2<f(S_2)=3, we can merge S_5,S_2 into S_6={1,2,3}.
For the first requirement, S_4={2,3}=\{a_2,a_3}, satisfies it, thus k_1=4.
For the second requirement, S_6={1,2,3}=\{a_1,a_2,a_3}, satisfies it, thus k_2=6
Notice that unused sets, identical sets, outputting the same set multiple times, and using sets that are present initially are all allowed.
inputFormat
Input
The first line contains two integers n,q (1≤ n ≤ 2^{12},1 ≤ q ≤ 2^{16}) — the length of the permutation and the number of needed sets correspondently.
The next line consists of n integers a_1,a_2,⋅⋅⋅, a_n (1≤ a_i≤ n, a_i are pairwise distinct) — given permutation.
i-th of the next q lines contains two integers l_i,r_i (1≤ l_i≤ r_i≤ n), describing a requirement of the i-th set.
outputFormat
Output
It is guaranteed that a solution under given constraints exists.
The first line should contain one integer cnt_E (n≤ cnt_E≤ 2.2× 10^6), representing the number of sets after all operations.
cnt_E-n lines must follow, each line should contain two integers u, v (1≤ u, v≤ cnt', where cnt' is the value of cnt before this operation), meaning that you choose S_u, S_v and perform a merging operation. In an operation, g(S_u)<f(S_v) must be satisfied.
The last line should contain q integers k_1,k_2,⋅⋅⋅,k_q (1≤ k_i≤ cnt_E), representing that set S_{k_i} is the ith required set.
Please notice the large amount of output.
Examples
Input
3 2 1 3 2 2 3 1 3
Output
6 3 2 1 3 5 2 4 6
Input
2 4 2 1 1 2 1 2 1 2 1 1
Output
5 2 1 2 1 2 1 5 3 3 1
Note
In the first sample:
We have S_1={1},S_2={3},S_3={2} initially.
In the first operation, because g(S_3)=2<f(S_2)=3, we can merge S_3,S_2 into S_4={2,3}.
In the second operation, because g(S_1)=1<f(S_3)=2, we can merge S_1,S_3 into S_5={1,2}.
In the third operation, because g(S_5)=2<f(S_2)=3, we can merge S_5,S_2 into S_6={1,2,3}.
For the first requirement, S_4={2,3}=\{a_2,a_3}, satisfies it, thus k_1=4.
For the second requirement, S_6={1,2,3}=\{a_1,a_2,a_3}, satisfies it, thus k_2=6
Notice that unused sets, identical sets, outputting the same set multiple times, and using sets that are present initially are all allowed.
样例
2 4
2 1
1 2
1 2
1 2
1 1
3
2 1
3 3 3 1