Chris is learning about segment tree beats and decided to make a template problem about it. You are given an array ~a~ of length ~N~ and ~Q~ queries.

1 l r x: Determine how many ~a_i = x~ where ~l \leq i \leq r~

2 l r x: for ~l \leq i \leq r~, ~a_i~ becomes ~(a_i + x) \pmod{10^5+3}~

3 l r x: for ~l \leq i \leq r~, ~a_i~ becomes ~(a_i \times x) \pmod{10^5+3}~

Input Specification

The first line of input contains two integers ~N\ (1 \leq N \leq 2\cdot 10^5), Q\ (1 \leq Q \leq 2\cdot 10^5)~.

The next line contains ~N~ integers ~a_i\ (0 \leq a_i < 10^5+3)~.

The next ~Q~ lines contain a query as described above. For all queries, ~1 \leq L \leq R \leq N~ and ~0 \leq x < 10^5+3~.

Output Specification

For each query of type 1, you are to output the answer on one line.

Subtasks

Subtask 1 (5%)

~N,Q \leq 10^4~

Subtask 2 (95%)

No further constraints.

Sample Input

5 5
1 2 3 4 5
1 2 3 3
3 2 4 50002
1 1 5 1
2 1 3 1
1 1 4 2

Sample Output

1
2
3