Codeforces Round 763 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

dfs and similar

implementation

sortings

*1100

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Game on Ranges

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAlice and Bob play the following game. Alice has a set $$$S$$$ of disjoint ranges of integers, initially containing only one range $$$[1, n]$$$. In one turn, Alice picks a range $$$[l, r]$$$ from the set $$$S$$$ and asks Bob to pick a number in the range. Bob chooses a number $$$d$$$ ($$$l \le d \le r$$$). Then Alice removes $$$[l, r]$$$ from $$$S$$$ and puts into the set $$$S$$$ the range $$$[l, d - 1]$$$ (if $$$l \le d - 1$$$) and the range $$$[d + 1, r]$$$ (if $$$d + 1 \le r$$$). The game ends when the set $$$S$$$ is empty. We can show that the number of turns in each game is exactly $$$n$$$.

After playing the game, Alice remembers all the ranges $$$[l, r]$$$ she picked from the set $$$S$$$, but Bob does not remember any of the numbers that he picked. But Bob is smart, and he knows he can find out his numbers $$$d$$$ from Alice's ranges, and so he asks you for help with your programming skill.

Given the list of ranges that Alice has picked ($$$[l, r]$$$), for each range, help Bob find the number $$$d$$$ that Bob has picked.

We can show that there is always a unique way for Bob to choose his number for a list of valid ranges picked by Alice.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). Description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 1000$$$).

Each of the next $$$n$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$), denoting the range $$$[l, r]$$$ that Alice picked at some point.

Note that the ranges are given in no particular order.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$, and the ranges for each test case are from a valid game.

Output

For each test case print $$$n$$$ lines. Each line should contain three integers $$$l$$$, $$$r$$$, and $$$d$$$, denoting that for Alice's range $$$[l, r]$$$ Bob picked the number $$$d$$$.

You can print the lines in any order. We can show that the answer is unique.

It is not required to print a new line after each test case. The new lines in the output of the example are for readability only.

Example

Input

4 1 1 1 3 1 3 2 3 2 2 6 1 1 3 5 4 4 3 6 4 5 1 6 5 1 5 1 2 4 5 2 2 4 4

Output

1 1 1 1 3 1 2 2 2 2 3 3 1 1 1 3 5 3 4 4 4 3 6 6 4 5 5 1 6 2 1 5 3 1 2 1 4 5 5 2 2 2 4 4 4

Note

In the first test case, there is only 1 range $$$[1, 1]$$$. There was only one range $$$[1, 1]$$$ for Alice to pick, and there was only one number $$$1$$$ for Bob to pick.

In the second test case, $$$n = 3$$$. Initially, the set contains only one range $$$[1, 3]$$$.

- Alice picked the range $$$[1, 3]$$$. Bob picked the number $$$1$$$. Then Alice put the range $$$[2, 3]$$$ back to the set, which after this turn is the only range in the set.
- Alice picked the range $$$[2, 3]$$$. Bob picked the number $$$3$$$. Then Alice put the range $$$[2, 2]$$$ back to the set.
- Alice picked the range $$$[2, 2]$$$. Bob picked the number $$$2$$$. The game ended.

In the fourth test case, the game was played with $$$n = 5$$$. Initially, the set contains only one range $$$[1, 5]$$$. The game's turn is described in the following table.

Game turn | Alice's picked range | Bob's picked number | The range set after |

Before the game start | $$$ \{ [1, 5] \} $$$ | ||

1 | $$$[1, 5]$$$ | $$$3$$$ | $$$ \{ [1, 2], [4, 5] \}$$$ |

2 | $$$[1, 2]$$$ | $$$1$$$ | $$$ \{ [2, 2], [4, 5] \} $$$ |

3 | $$$[4, 5]$$$ | $$$5$$$ | $$$ \{ [2, 2], [4, 4] \} $$$ |

4 | $$$[2, 2]$$$ | $$$2$$$ | $$$ \{ [4, 4] \} $$$ |

5 | $$$[4, 4]$$$ | $$$4$$$ | $$$ \{ \} $$$ (empty set) |

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/19/2024 20:54:39 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|