AT_abc431_g [ABC431G] One Time Swap 2

You are given an integer sequence $ A=(A_1,A_2,\ldots,A_N) $ of length $ N $ . For a pair of integers $ (l, r) \ (1\leq l\lt r\leq N) $ , let $ f(l,r) $ be the integer sequence obtained by swapping the $ l $ -th element and the $ r $ -th element of $ A $ . Generate a sequence of integer sequences $ B=(B_1,B_2,\ldots,B_{\frac{N(N-1)}{2}}) $ of length $ \frac{N(N-1)}{2} $ by the following procedure: - Prepare an empty sequence $ B=() $ . - For each pair of integers $ (l, r)\ (1\leq l\lt r\leq N) $ , add $ f(l,r) $ to $ B $ . - Sort $ B $ in lexicographical order of sequences. You are given $ Q $ queries; process them in order. The $ i $ -th query is as follows: - Given an integer $ k $ , find one pair of integers $ (l, r) \ (1\leq l\lt r\leq N) $ such that $ B_k=f(l,r) $ and output it. What is lexicographical order of sequences?A sequence $ S = (S_1,S_2,\ldots,S_{|S|}) $ is **lexicographically smaller** than a sequence $ T = (T_1,T_2,\ldots,T_{|T|}) $ if and only if one of the following two conditions holds. Here, $ |S| $ and $ |T| $ represent the lengths of $ S $ and $ T $ , respectively. 1. $ |S| \lt |T| $ and $ (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}) $ . 2. There exists an integer $ 1 \leq i \leq \min\lbrace |S|, |T| \rbrace $ such that both of the following hold: - $ (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1}) $ - $ S_i $ is smaller than $ T_i $ (as a number).

The input is given from Standard Input in the following format: > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ Each query is given in the following format: > $ k $

Output $ Q $ lines. The $ i $ -th line should contain the answer to the $ i $ -th query in the following format: > $ l $ $ r $ If there are multiple solutions, any of them will be considered correct.

### Sample Explanation 1 $ f(1, 2) = (2, 1, 1, 2), f(1, 3) = (1, 2, 1, 2), f(1, 4) = (2, 2, 1, 1), f(2, 3) = (1, 1, 2, 2), f(2, 4) = (1, 2, 1, 2), f(3, 4) = (1, 2, 2, 1) $ . The sequence $ B $ obtained by sorting these six sequences in lexicographical order is $ B=((1, 1, 2, 2), (1, 2, 1, 2), (1, 2, 1, 2), (1, 2, 2, 1), (2, 1, 1, 2), (2, 2, 1, 1)) $ . - For the $ 1 $ -st query, the only $ (l,r) $ such that $ B_1=(1,1,2,2)=f(l,r) $ is $ (l,r)=(2,3) $ . - For the $ 2 $ -nd query, $ (l,r) $ such that $ B_3=(1,2,1,2)=f(l,r) $ are $ (l,r)=(1,3),(2,4) $ . In this case, either one will be considered correct. - For the $ 3 $ -rd query, the only $ (l,r) $ such that $ B_5=(2,1,1,2)=f(l,r) $ is $ (l,r)=(1,2) $ . ### Constraints - $ 2\leq N\leq 2\times 10^5 $ - $ 1\leq Q\leq 2\times 10^5 $ - $ 1\leq A_i\leq N $ - $ 1\leq k\leq \frac{N(N-1)}{2} $ - All input values are integers.