Problem Description

Given $n$ points $(x_i, y_i)_{i=1}^n$, you need to process $m$ operations in order. Each operation gives $o, x, y, X, Y$.

• First, perform an update:
  • If $o = 1$, then for all points satisfying $x_i \le x,\; y_i \le y$, set their $y_i$ to $y$.
  • If $o = 2$, then for all points satisfying $x_i \le x,\; y_i \le y$, set their $x_i$ to $x$.
• Then perform a query: ask for the number of points satisfying $x_i \le X,\; y_i \le Y$.

Input Format

The first line contains two integers $n, m$.

The next $n$ lines each contain two integers $x_i, y_i$.

The next $m$ lines each contain five integers $o, x, y, X, Y$, representing one operation.

Output Format

Output $m$ lines, each containing one integer. In order, output the answer to the query in each operation.

5 6
1 2
3 1
5 1
3 5
4 4
1 4 2 5 4
1 4 3 5 3
2 3 5 1 3
2 2 3 1 4
1 3 3 1 4
2 5 5 2 1

4
3
0
0
0
0

Hint

Idea: ccz181078, Solution: ccz181078, Code: ccz181078, Data: ccz181078.

Constraints: For all testdata, $1 \le n, m \le 10^6$, and $1 \le x_i, y_i, x, y, X, Y \le n$.

Subtask 1 (20 points): $n, m \le 10^3$.

Subtask 2 (20 points): $x_i, y_i, x, y, X, Y$ are independently chosen uniformly at random from $1$ to $n$.

Subtask 3 (20 points): $o = 1$.

Subtask 4 (20 points): $n, m \le 3 \times 10^5$, depends on Subtask 1.

Subtask 5 (20 points): No special restrictions, depends on Subtasks 1, 2, 3, 4.

Translated by ChatGPT 5