F. Auchenai's Letter Game
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Auchenai is playing with his new letter game with a whole bunch of letter tiles available! More specifically, he has $$$a$$$ tiles of the letter $$$\tt{I}$$$, $$$b$$$ tiles of the letter $$$\tt{G}$$$, and $$$c$$$ tiles of the letter $$$\tt{M}$$$.

You are given positive integers $$$x$$$, $$$y$$$, and $$$z$$$. For any string $$$s$$$ that Auchenai constructs, he scores it as follows:

  • For every occurrence of the substring $$$\tt{IGM}$$$ in $$$s$$$, add $$$x$$$ points.
  • For every occurrence of the substring $$$\tt{GM}$$$ in $$$s$$$, add $$$y$$$ points.
  • For every occurrence of the substring $$$\tt{IM}$$$ in $$$s$$$, add $$$z$$$ points.

Note that substrings may overlap. For example, the string $$$\tt{IGMM}$$$ contains one occurrence of $$$\tt{IGM}$$$ and one occurrence of $$$\tt{GM}$$$ and thus would score $$$x+y$$$ points.

Auchenai wants to arrange all tiles into a single string of length $$$a + b + c$$$ so that its total score is maximized. Please help him achieve his goal!

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The next $$$t$$$ lines each contain six integers: $$$a, b, c, x, y, z$$$ ($$$0 \leq a, b, c \leq 2 \cdot 10^5$$$, $$$a+b+c \gt 0$$$, $$$1 \leq x, y, z \leq 10^9 $$$).

It is guaranteed that the sum of $$$a+b+c$$$ over all test cases does not exceed $$$6\cdot 10^5$$$.

Output

For each of the test cases, print two lines. In the first line, print the maximum possible score. In the second line, output any string consisting of $$$a$$$ $$$\tt{I}$$$'s, $$$b$$$ $$$\tt{G}$$$'s, and $$$c$$$ $$$\tt{M}$$$'s that achieves the maximum score.

Example
Input
8
1 1 1 5 3 2
3 1 3 10 4 7
2 2 2 100 5 6
3 3 3 10 1 2
5 4 0 100 100 100
4 0 3 100 7 5
2 2 2 3 4 5
4 3 4 1 3 10
Output
8
IGM
28
IGMIMIM
210
IGMIGM
33
IGMIGMIGM
0
IIIIIGGGG
15
IMIMIMI
14
IGMIGM
40
IMIMIMIMGGG