eolymp
bolt
Try our new interface for solving problems
Problems

New White-Black Tree

New White-Black Tree

Time limit 7 seconds
Memory limit 512 MiB

Naomi has learnt about Red-Black trees, now it's time to learn about White-Black trees. She is reading an algorithms book. Some pages contain pictures of trees, but the edges of the trees faded out through all these years. According to the text, each of these edges should be either white or black.

Naomi noticed that each vertex has two integers written beside it. She guessed that the first integer is the number of white edges incident to the vertex, and the second is the number of black edges incident to the vertex.

Naomi recreated all the pictures. Can you do that?

Input data

The first line contains an integer t — the number of pictures to recreate (1 \le t \le 3 \cdot 10^5).

The following lines describe t pictures. Each description starts with a line containing an integer n — the number of vertices in the tree (1 \le n \le 3 \cdot 10^5).

The i-th of the following n lines of the picture description contains two integers w_i and b_i — two integers written beside the i-th vertex of the tree: the number of white and black edges incident to the i-th vertex (0 \le w_i, b_i \le n - 1).

It is guaranteed that the sum of n over all the pictures does not exceed 3 \cdot 10^5.

Output data

Print t blocks of output, the i-th of which should contain the information about recreating picture i.

In the first line of each block print "No" if there is no way, and "Yes" if there is at least one way to recreate the picture. If there is a way to recreate the picture of the tree, print additional n - 1 lines, each of them containing two integers and a letter 'W' for white or 'B' for black: v_i, u_i and c_i, defining an edge between vertices v_i and u_i of color c_i (1 \le v_i, u_i \le n; c_i is either 'W' or 'B').

If there are multiple ways to recreate a picture, you can print any of them. The edges of the tree can be printed in any order.

Examples

Input example #1
6
4
1 1
1 1
1 0
1 0
4
1 0
2 1
1 1
1 0
1
0 0
2
0 1
0 1
2
1 0
0 1
3
2 0
0 1
0 1
Output example #1
Yes
1 4 W
2 3 W
2 1 B
No
Yes
Yes
2 1 B
No
No
Author Niyaz Nigmatullin