Army Buddies

Time limit1sMemory limit128 MB

Summary

After each loss report removes living soldiers L through R, print the nearest surviving neighbors on both sides, or * when none exists.

Level: Medium4 of 10
Topics: Union-find, Linked list, Implementation
Solved: No attempts yet

Problem

Soldiers stand in a single line, numbered from $1$ to $S$ from left to right. Besides protecting himself and attacking the enemy, each soldier must also protect his two nearest neighbors — one immediately to his left and one immediately to his right. These two neighbors are called his buddies. The leftmost soldier has no left buddy, and the rightmost soldier has no right buddy.

If a soldier's left or right buddy is killed, then the next living soldier in that direction becomes his new buddy.

As the battle rages, soldiers are killed. Each time losses occur, the army's information system must tell the soldiers who their new buddies are. Each loss report describes a group of contiguous soldiers that were just killed.

For each loss report, write a program that prints the new buddies formed by removing that group from the line: the first surviving soldier immediately to the left of the removed group, and the first surviving soldier immediately to its right.

Input

The input consists of several test cases.

The first line of each test case contains two integers $S$ and $B$ : the number of soldiers in the line and the number of loss reports ( $1 \le B \le S \le 10^5$ ). Soldiers are numbered from $1$ to $S$ by their position, where $1$ is the leftmost soldier and $S$ is the rightmost.

Each of the next $B$ lines describes one loss report with two integers $L$ and $R$ ( $1 \le L \le R \le S$ ), meaning that soldiers $L$ through $R$ were just killed. You may assume that all of these soldiers were alive up to that moment.

The last test case is followed by a line containing two zeros.

Output

For each test case, output $B+1$ lines.

On the $i$ -th line, for the $i$ -th loss report L R, print the newly formed buddies after removing soldiers $L$ through $R$ : the first surviving soldier to the left of $L$ and the first surviving soldier to the right of $R$ , separated by a single space. If there is no surviving soldier in a direction, print an asterisk * in its place.

After each test case, print a line containing a single hyphen -.

Examples7

Example 1

Input

Expected output

* *
-
1 6
1 10
* 10
* *
-
* 2
-

Example 2
Input
```
5 1
1 5
0 0
```
Expected output
```
* *
-
```
Example 3
Input
```
5 1
3 3
0 0
```
Expected output
```
2 4
-
```
Example 4
Input
```
6 3
1 1
2 2
3 4
0 0
```
Expected output
```
* 2
* 3
* 5
-
```
Example 5
Input
```
6 2
6 6
4 5
0 0
```
Expected output
```
5 *
3 *
-
```

Example 6

Input

Expected output

1 3
-
* 2
3 *
-

Example 7
Input
```
4 3
2 3
1 1
4 4
0 0
```
Expected output
```
1 4
* 4
* *
-
```