P-OldGrid
Little Perica owns an old grid of LED diodes. They are not regular LED diodes, they're what you might call "hyper-diodes", since they have more states than just an ON/OFF state. They can have a very large number of states, each corresponding to integers in the range of 1 to 100000. One day, Perica decided that he wants to play with his old grid again. He noticed that all the states are in the beginning set to a pre-set value of D, however, since the grid is very old, it is impossible to change the state of a lot of the diodes on the grid.
Perica is interested in knowing, at any given moment, the product of all the state values within some rectangular subset of the grid. Unfortunately he hasn't programmed in a long while, so he asked you to help him.
From the first line of the standard input read the integers N (1 <= N <= 50000), Q (1 <= Q <= 50000) and D (1 <= D <= 100000), representing the amount of LEDs that can be altered, the amount of commands to be given, and the initial state of each LED in the grid, respectively.
Each of the following N lines contains two integers xi and yi (1 <= xi, yi <= 100000, 1 <= i <= N), representing the coordinates of the i-th LED whose state Perica can alter.
Finally, in each of the following Q lines there will be a command description. Commands can be of the form:
SET i x, which sets the state with the value x on the i-th LED in the active list;
SWAP i j, which swaps the values of the i-th and j-th LED in the active list;
QUERY x y a b, which asks you to determine the product of all the LEDs in the rectangle with lower-left corner in (x, y), width a and height b.
2 5 5
1 1
2 2
QUERY 1 1 2 2
SET 1 10
QUERY 1 1 2 2
SWAP 1 2
QUERY 1 1 1 1Output:
625
1250
5Explanation: Initially, all the LEDs in the grid are set to 5. Since the first rectangle query contains four fields, the product is in this case 5^4 = 625. After setting the cell (1,1) to 10, the product becomes 10 * 5^3 = 1250. After swapping cells (1,1) and (2,2), the value in the cell (1,1) is back to 5.
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.