E. Production Line
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a sequence $$$a$$$ of length $$$n$$$. Your task is to process $$$q$$$ events of the following $$$4$$$ types:

  1. Given $$$x, y$$$ and $$$z$$$, for each $$$1 \leq i \leq n$$$ satisfying $$$x \leq a_i \leq y$$$ change $$$a_i$$$ to $$$z$$$.
  2. Given $$$l, r$$$ and $$$c$$$, for each $$$l \leq i \leq r$$$ change $$$a_i$$$ to $$$c$$$.
  3. Given $$$p$$$, print $$$a_p$$$.
  4. Given $$$p$$$, print the number of $$$1 \leq i \leq n$$$ satisfying $$$a_i \gt a_p$$$.
Input

The first line of input contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 200\,000$$$). The next line contains $$$n$$$ integers — $$$i$$$-th of them represents $$$a_i$$$ ($$$1 \leq a_i \leq 10^9$$$). The next $$$q$$$ lines contain descriptions of events. Each line starts with one number $$$t$$$ ($$$1 \leq t \leq 4$$$) representing the type of the event. If:

  1. $$$t = 1$$$ then numbers $$$x, y$$$ and $$$z$$$ follow ($$$1 \leq x \leq y \leq 10^9$$$, $$$1 \leq z \leq 10^9$$$);
  2. $$$t = 2$$$ then numbers $$$l, r$$$ and $$$c$$$ follow ($$$1 \leq l \leq r \leq n$$$, $$$1 \leq c \leq 10^9$$$).
  3. $$$t = 3$$$ or $$$t = 4$$$, then one number $$$p$$$ follows ($$$1 \leq p \leq n$$$).
Output

Output one line for each query of type $$$3$$$ or $$$4$$$. The $$$i$$$-th of them should contain the answer for the $$$i$$$-th such query from the input.

Example
Input
5 8
1 2 3 2 1
4 5
1 1 1 4
4 3
2 1 2 1
4 4
2 2 3 7
4 1
3 4
Output
3
2
2
4
2