You are given an array x of distinct integers of length n. Now you have to execute q queries of two types of the following form:
• 1 l r m : Find the number of values less than m(0 ≤ m ≤ 10^9) from the array x in range l to r (1 ≤ l ≤ n; 1 ≤ r ≤ n; l ≤ r ) (inclusive).
• 2 l r : Swap array x values of position l( 1 ≤ l ≤ n) and r( 1 ≤ r ≤ n).
The first line contains two integers n and q ( 1 ≤ n ≤ 300000, 1 ≤ q ≤ 300000 ) the length of the arrays and the number of queries correspondingly. The second line contains array x. Next q lines contain queries in the form described in the statement.
For each query of first type print the result on a single line.
Input | Output |
---|---|
15 10 297 202 534 231 559 748 286 481 27 560 175 1 945 978 300 1 2 2 381 1 4 5 420 2 10 13 2 1 7 2 5 12 1 6 12 274 2 1 2 2 8 9 2 13 13 1 8 12 433 | 1 1 2 2 |