409572: GYM103634 C Jump

In a very large $$$2 \cdot 10^9 \times 2 \cdot 10^9$$$ grid, there are initially $$$N$$$ active points with known coordinates.

You are also given $$$Q$$$ queries, which you will have to process in order. Each query can be of either one of the following two types:

1. ! x y — Toggle the state of the point at coordinates $$$(x,y)$$$. If the point at $$$(x,y)$$$ used to be active, it will now be inactive, and vice-versa.
2. ? x1 y1 x2 y2 — Print the number of ways to get from an active point at coordinates $$$(x_1,y_1)$$$ to another active point at coordinates $$$(x_2,y_2)$$$ by only jumping through active points. It is possible to jump from an active point $$$(a,b)$$$ to another active point $$$(c,d)$$$ if and only if $$$a < c$$$. Since the number of ways to get from $$$(x_1,y_1)$$$ to $$$(x_2,y_2)$$$ can be very large, print its remainder modulo $$$10^9+7$$$.

The first line of input contains two integers $$$N$$$ and $$$Q$$$ ($$$1 \le N, Q \le 3 \cdot 10^5$$$) — the number of initial active points, and the number of queries, respectively.

The second line of input contains $$$N$$$ integers $$$x_1,x_2,\ldots,x_n$$$ ($$$-10^9 \le x_i \le 10^9$$$), the $$$x$$$-coordinates of the initially active points.

The third line of input contains $$$N$$$ integers $$$y_1,y_2,\ldots,y_n$$$ ($$$-10^9 \le y_i \le 10^9$$$), the $$$y$$$-coordinates of the initially active points.

It is guaranteed that all $$$N$$$ points are pairwise distinct.

The next $$$Q$$$ lines contain the descriptions of the queries, one line per query:

Each query can have one of the following two formats:

1. ! x y. In this case, it is guaranteed that $$$-10^9 \le x,y \le 10^9$$$;
2. ? x1 y1 x2 y2. In this case, it is guaranteed that $$$-10^9 \le x_1,y_1,x_2,y_2 \le 10^9$$$ and that both $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ are active points.

For every second type query, print one integer, the number of ways to get from $$$(x_1,y_1)$$$ to $$$(x_2,y_2)$$$ by only jumping through active points. Since this number can be very large, print its remainder modulo $$$10^9+7$$$.

7 7
-1 -2 2 -1 0 3 -3
-2 -1 0 1 3 3 4
? -1 -2 3 3
? 2 0 2 0
? 3 3 -1 -2
! 2 2
? -2 -1 0 3
! -2 -1
? -3 4 3 3

4
1
0
3
18

The $$$7$$$ initial active points

For the first query, the $$$4$$$ paths from $$$(-1,-2)$$$ to $$$(3,3)$$$ are:

1. $$$(-1,-2) \to (3,3)$$$;
2. $$$(-1,-2) \to (0,3) \to (3,3)$$$;
3. $$$(-1,-2) \to (2,0) \to (3,3)$$$;
4. $$$(-1,-2) \to (0,3) \to (2,0) \to (3,3)$$$

For the second query, it is possible to get from $$$(2,0)$$$ to $$$(2,0)$$$ only by not jumping at all.

For the third query, it is impossible to get from $$$(3,3)$$$ to $$$(-1,2)$$$.

The fourth query toggles the state of point $$$(2,2)$$$, making it active. Similarly, the $$$6$$$-th query deactivates point $$$(-2,-1)$$$.