Carrot Farm

Interview

Time limit3sMemory limit512 MB

Summary

Maintain a set of disjoint planted intervals under plant and harvest operations; after each, report the empty or planted area directly left and right of the affected span. Each area is (number of columns) times L.

Level: Medium6 of 10
Topics: Intervals, Tree, Simulation, Implementation
Solved: No attempts yet

Problem

Farmer Yam bought a piece of land and will turn it into a carrot farm. The land is a rectangle that is $W$ ( $1 \le W \le 10^8$ ) units wide and $L$ ( $1 \le L \le 10$ ) units long, and Yam thinks of it as an integer grid. The cells are numbered $0, 1, \dots, L-1$ along the length and $0, 1, \dots, W-1$ along the width.

Yam wrote down a plan of $n$ ( $1 \le n \le 50000$ ) actions. There are only two kinds of actions, planting seeds and harvesting, and Yam can mix them in any order. The land is empty at the start. Simulate the plan and report two numbers for every action.

A planting action plant a b sows seeds in cells $a$ to $b$ along the width, over the full length of the land. The new area never overlaps an existing plantation, but it may touch one. Plantations that touch are merged into a single plantation. After the merge, report the area of the empty land that lies immediately to the left of the plantation just created, and then the area of the empty land that lies immediately to its right.

A harvesting action harvest a b harvests cells $a$ to $b$ along the width, over the full length of the land. A harvest can split one plantation into two. Every harvested area lies completely inside a single plantation. Report the area of the planted land that lies immediately to the left of the area just harvested, and then the area of the planted land that lies immediately to its right.

An area is the number of cells along the width multiplied by $L$ . When there is no such land, report 0.

Input

The first line contains the number of test cases $T$ ( $1 \le T \le 7$ ).

Each test case starts with a line that holds three space separated integers $W$ , $L$ , and $n$ .

Each of the next $n$ lines describes one action in the form action a b, where action is either plant or harvest, and $a$ and $b$ ( $0 \le a \le b \le W-1$ ) are the lowest and the highest cell number the action covers.

Output

For each action, print the two numbers you have to report on their own line, separated by a single space.

After the last action of every test case, print a line that contains only --, without the quotes.

Examples3

Example 1

Input

2
7 2 7
plant 1 2
plant 5 6
plant 3 4
harvest 3 3
plant 3 3
harvest 4 5
harvest 2 2
4 5 1
plant 1 2

Expected output

Example 2

Input

1
1 1 4
plant 0 0
harvest 0 0
plant 0 0
harvest 0 0

Expected output

Example 3

Input

1
10 10 6
plant 0 9
harvest 0 9
plant 3 5
plant 0 2
plant 6 9
harvest 4 4

Expected output