A. Range Affine Update and Modulo Query
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given an array of $$$n$$$ integers, your task is to process $$$q$$$ queries of the following types:

  • Update: For a given interval $$$[l, r]$$$, update each element $$$a_i$$$ in the interval to $$$(a_i \times c + d)$$$, where $$$c$$$ and $$$d$$$ are given integers.
  • Query: Given integers $$$l, r, x$$$, report the number of elements in the interval $$$[l, r]$$$ whose value modulo $$$10^5 + 3$$$ is equal to $$$x$$$, i.e., $$$$$$ \begin{aligned} \#\{i \mid l \le i \le r, \ a_i \bmod (10^5 + 3) = x\} \end{aligned} $$$$$$
Note that $$$10^5 + 3$$$ is prime.
Input

The first line contains two integers $$$n$$$ and $$$q$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ The next $$$q$$$ lines each describe a query in one of the following formats:

  • 1 l r c d — representing an Update query.
  • 2 l r x — representing a Query query.
  • $$$1 \leq n \le 10^6$$$
  • $$$1 \leq q \le 10^4$$$
  • $$$1 \leq a_i, c, d, x \leq 10^5$$$
  • $$$1 \leq l \leq r \leq n$$$
Output

Print the result of each 2 l r x query.

Example
Input
5 5
1 1 2 3 3
1 1 3 2 1
2 1 4 3
1 2 4 2 3
2 1 5 9
2 2 3 3
Output
3
2
0