406953: GYM102623 L Lottery Tickets

Setsuna is almost out of money! Therefore, she always thinks about ways to get rich overnight.

She finds that buying lottery tickets is a wonderful choice, and she decides to use her lucky number as the lottery number.

Setsuna uses some unique methods to pick her lucky numbers. She will first select $$$n$$$ magic cards. Each card is written with a digit between $$$0$$$ and $$$9$$$ inclusively. Then she will use some cards to construct a number. She believes that the largest number she can construct which can be divided by 4 is her lucky number.

It is unnecessary to use all the cards, and it is possible that such lucky number does not exist.

Because she is daydreaming of getting rich, only you can help her find this lucky number.

The input consists of multiple test cases.

The first line contains a single integer $$$t(1 \leq t \leq 3 \times 10^5)$$$, indicating the number of test cases.

Each of the next $$$t$$$ lines contains $$$10$$$ integers $$$c_0,c_1,\cdots,c_{9}(0 \leq c_i \leq 10^5,\sum_{i=0}^9 c_i > 0)$$$, where $$$c_i$$$ indicates the number of cards written with number $$$i$$$.

It is guaranteed that the sum of $$$\sum_{i=0}^9 c_i$$$ of all test cases does not exceed $$$3 \times 10^5$$$.

For each test case given in the input, print the lucky number(without leading zero) or $$$-1$$$ if such lucky number does not exist.

6
0 1 1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
1 0 0 2 0 0 0 0 0 0
2 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1

12
4
0
98765432100
9876543120
987654312