F. Keys
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

To pass the time, Bessie the cow and her friend Elsie like to play a version of a game they saw at the county fair.

To start, Bessie puts three inverted shells on a table and places a small round pebble under one of them. Bessie then proceeds to swap pairs of shells, while Elsie tries to guess the location of the pebble.

But Elsie has gotten too good at this game. So Bessie summons a floating grid of $$$2^n \times 2^n$$$ keys. The rows are labeled $$$0 \dots 2^n - 1$$$, and the columns are labeled $$$0 \dots 2^n - 1$$$.

Bessie then points to $$$m$$$ of the keys and tells Elsie to keep track of the keys.

Afterwards, Bessie uses her super cow powers to perform $$$k$$$ operations. In each operation, she selects $$$x, y$$$. Then, the grid of keys is partitioned into subgrids with $$$2^x$$$ rows and $$$2^y$$$ columns. Then, she rotates each subgrid $$$180$$$ degrees and joins the subgrids back together. After performing all $$$k$$$ operations, she asks Elsie to guess the locations of the keys she pointed to at the beginning.

Elsie could not keep up with Bessie's super cow powers. Help Elsie determine the locations of the keys that Bessie pointed to.

Input

The first line contains $$$n \ (1 \leq n \leq 60)$$$, $$$m \ (1 \leq m \leq 5 \cdot 10^5)$$$, and $$$k \ (1 \leq k \leq 5 \cdot 10^5)$$$ – the grid size, the number of keys Bessie points to, and the number of operations.

The next $$$m$$$ lines contain $$$r \ (0 \leq r \leq 2^n-1)$$$ and $$$c \ (0 \leq c \leq 2^n-1)$$$ – the row and column of the keys that Bessie points to.

The next $$$k$$$ lines contain $$$x \ (0 \leq x \leq n)$$$ and $$$y \ (0 \leq y \leq n)$$$ – the $$$x$$$ and $$$y$$$ values for each of Bessie's operations.

–

Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Tests $$$1-6$$$ satisfy $$$m \leq 1000$$$, and $$$k \leq 1000$$$.

Tests $$$7-8$$$ satisfy $$$n \leq 30$$$.

Tests $$$9-20$$$ satisfy no additional constraints.

Output

$$$m$$$ lines; each line contains $$$r'$$$ and $$$c'$$$, denoting the new row and column of each key after Bessie uses her super cow powers, in the same order that Bessie pointed to the keys.

Example
Input
2 1 4
1 2
0 1
1 1
2 0
2 2
Output
0 1
Note

FOCUS

—

Problem Idea: culver0412

Problem Preparation: Jasonwei08

Occurrences: Novice F