This problem is a harder version of https://dmoj.ca/problem/wac6p6. In this version, you should aim to collect at least ~46~ candy canes.

With the Christmas season finally over, Santa has decided to let you collect the leftover candy canes from each of his ~T~ factories. Each factory has ~100~ remaining candy canes consisting of three colours: red, green, and blue. At each factory, you will be given two bowls to collect the remaining candy canes. At any point in time, each bowl must not contain two candy canes of different colours. The candy canes will come off a conveyor belt one by one and you will have a choice to place the candy cane in one of the two bowls or discard the candy cane in the trash. In addition, before placing the candy cane in a bowl, you will be allowed to empty any number of bowls into the trash, throwing away their contents. The next candy cane will not appear until you place the current candy cane in one of the two bowls or discard it. Once you place or discard the last candy cane, you will move on to the next factory.

In order to help you out, Santa has told you the distribution of the candy canes, except he has left out the colours. All he will give you is ~3~ numbers that sum to ~100~. You will only be allowed to keep the candy canes in the two bowls when you leave each factory. How many candy canes can you obtain? See the scoring section for more details.

Scoring

For this problem, you will NOT be required to pass ANY of the samples in order to receive points.

Your score will depend on the minimum number of candy canes you obtain over all factories. The number of candy canes you obtain is equal to the sum of the number of candy canes in the two bowls when you leave each factory. Let ~x~ be the minimum number of candy canes you obtain over all factories.

~x~	Score
~0 \le x \le 33~	~0\%~
~34 \le x \le 39~	~20\%~
~40 \le x \le 42~	~40\%~
~43 \le x \le 45~	~70\%~
~46 \le x \le 100~	~100\%~

Note that a score of ~0\%~ will receive a verdict of Wrong Answer (with no additional test cases being executed), a score above ~0\%~ but below ~100\%~ will receive a verdict of Partially Accepted, and a score of ~100\%~ will receive a verdict of Accepted. The judge will also provide feedback with your verdict for each test case.

Your score for the problem is equal to the minimum score for each test case.

Interaction

The first line contains the integer ~T~, the number of candy cane factories you will visit. For every test case in the data, ~T~ will be equal to ~100~.

For each factory, the first line will contain ~3~ integers, ~A~, ~B~, and ~C~. These correspond to the distribution of the candy canes. Specifically, there are ~A~ candy canes of one colour, ~B~ candy canes of a different colour, and ~C~ candy canes of the remaining colour. ~0 \le A, B, C \le 100~ and ~A + B + C = 100~ will always hold in the data.

You will then interact with the factory. For each of the ~100~ candy canes, the factory will output a single character consisting of either R, G, or B, followed by a \n character, indicating that the colour of the candy cane is either red, green, or blue. You will then be allowed to empty the first bowl by outputting EMPTY 1 (followed by a \n character) or empty the second bowl with EMPTY 2 (followed by a \n character). You may empty either bowl as many times as you want. When you are ready to place or discard the candy cane, you can output PLACE 1 (followed by a \n character) to place the candy cane in the first bowl, PLACE 2 (followed by a \n character) to place the candy cane in the second bowl, or DISCARD (please do not forget the \n character) to discard the candy cane in the trash. Remember that at any point in time, each bowl must not contain two candy canes of different colours. You will only receive the colour of the next candy cane after you place or discard the current candy cane. Once you place or discard the last candy cane, you must move on to the next factory.

The order that the candy canes appear on the conveyor belt is fixed beforehand and will not depend on any of your choices to place, discard, or empty.

If at any point you attempt an invalid operation (such as invalid output format, or two candy canes of different colours in the same bowl), -1 will be outputted (followed by a \n character of course). When this happens, you should terminate your program to avoid reading from a closed input stream, and you will receive a verdict of Wrong Answer. Otherwise, the verdict may be undefined.

Please note that you may need to flush stdout after each operation. In C++, this can be done with fflush(stdout) or cout << flush (depending on whether you use printf or cout). In Java, this can be done with System.out.flush(). In Python, you can use sys.stdout.flush().

Sample Interaction

The sample interaction does not comply with the problem statement and has ~T = 1~ and ~A + B + C = 10~. It will not appear in any of the test cases.

>>> denotes your output. Do not print this out.

1
5 2 3
G
>>> PLACE 2
G
>>> PLACE 1
B
>>> EMPTY 1
>>> PLACE 1
B
>>> EMPTY 2
>>> EMPTY 1
>>> PLACE 2
G
>>> DISCARD
G
>>> DISCARD
R
>>> PLACE 1
G
>>> DISCARD
B
>>> PLACE 2
R
>>> PLACE 1

Sample Explanation

In the end, you can keep ~4~ candy canes: ~2~ red candy canes in bowl ~1~ and ~2~ blue candy canes in bowl ~2~.