Simple Queries

robin_aust Replay of Intra AUST Prog...
Limits 4s, 512 MB

You are given an array x of distinct integers  x1,x2,x3xn(0xi109;1in)x_{1}, x_{2}, x_{3}… x_{n} (0 ≤ x_{i} ≤ 10^9 ; 1 ≤ i ≤ n) 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).

Input

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.

Output

For each query of first type print the result on a single line.

Sample

InputOutput
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

Submit

Login to submit.

Statistics

70% Solution Ratio
NirjhorEarliest, 1M ago
ash_98Fastest, 0.9s
ishaan_007Lightest, 4.3 MB
fragilisticShortest, 1641B
Toph uses cookies. By continuing you agree to our Cookie Policy.