F. audit
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

You are working as a quality control analyst at a precision manufacturing facility. Your job is to monitor the production line throughout your shift. Today, an internal audit is scheduled from the factory's management.

The production line generates $$$N$$$ measurements $$$a_1, a_2, \ldots, a_N$$$ throughout your shift. The management will issue $$$Q$$$ requests. For each request, they give you a range and a number $$$k$$$, and you have to report the minimum, the maximum and the $$$k$$$-th smallest measurement in that range.

Your task is to answer all of their requests. Luckily, you know management well: they only ever choose ranges of two standard lengths, $$$L_1$$$ or $$$L_2$$$.

Input

The first line contains two integers $$$N$$$ ($$$4 \leq N \leq 10^5$$$) and $$$Q$$$ ($$$1 \leq Q \leq 10^5$$$) — the number of measurements and the number of requests respectively.

The second line contains two integers $$$L_1$$$ ($$$3 \leq L_1 \leq N$$$) and $$$L_2$$$ ($$$3 \leq L_2 \leq N$$$) — the two standard lengths of the ranges.

The third line contains $$$N$$$ space separated integers $$$a_1, a_2, \ldots, a_N$$$ ($$$0 \leq a_i \leq 10^9$$$) — the measurements.

Each of the next $$$Q$$$ lines contains three integers $$$l$$$ ($$$l \in {1, 2}$$$), $$$i$$$ ($$$1 \leq i \leq N-L_{l}+1$$$) and $$$k$$$ ($$$2 \leq k \leq L_{l}-1$$$) — whether the range length is $$$L_1$$$ or $$$L_2$$$, the starting index of the range, and the order-statistic the management is interested in, respectively.

Output

Output $$$Q$$$ lines. For each request, print three integers: the minimum, the $$$k$$$-th smallest, and the maximum measurement in the specified range.

Example
Input
6 5
4 3
9 2 8 4 3 2
1 1 2
1 1 3
2 1 2
1 3 2
2 4 2
Output
2 4 9
2 8 9
2 8 9
2 3 8
2 3 4