Problem Statement

There are N dominoes numbered from 1 to N. The size of domino i is S_i.
Consider arranging some dominoes in a line from left to right and then toppling them. When domino i falls to the right, if the size of the domino placed immediately to the right of domino i is at most 2 S_i, then that domino also falls to the right.

You decided to choose two or more dominoes and arrange them in a line from left to right. The arrangement of dominoes must satisfy the following conditions:

• The leftmost domino is domino 1.
• The rightmost domino is domino N.
• When only domino 1 is toppled to the right, domino N eventually falls to the right as well.

Does an arrangement of dominoes satisfying the conditions exist? If it exists, what is the minimum number of dominoes that need to be arranged?

You are given T test cases, solve the problem for each of them.

Constraints

• 1 \leq T \leq 10^5
• 2 \leq N \leq 2 \times 10^5
• 1 \leq S_i \leq 10^9
• The sum of N over all test cases is at most 2 \times 10^5.
• All input values are integers.

Sample Input 1

3
4
1 3 2 5
2
1 100
10
298077099 766294630 440423914 59187620 725560241 585990757 965580536 623321126 550925214 917827435

Sample Output 1

4
-1
3

For the 1st test case, arranging the dominoes from left to right in the order domino 1, domino 3, domino 2, domino 4 satisfies the conditions in the problem statement. Specifically, for the 3rd condition, when only domino 1 is toppled to the right, the dominoes fall in the following order:

• Domino 3 is placed to the right of domino 1. Since the size of domino 3, S_3 = 2, is not greater than S_1 \times 2 = 1 \times 2 = 2, domino 3 also falls to the right.
• Domino 2 is placed to the right of domino 3. Since the size of domino 2, S_2 = 3, is not greater than S_3 \times 2 = 2 \times 2 = 4, domino 2 also falls to the right.
• Domino 4 is placed to the right of domino 2. Since the size of domino 4, S_4 = 5, is not greater than S_2 \times 2 = 3 \times 2 = 6, domino 4 also falls to the right.

It is impossible to achieve the conditions in the problem statement by arranging 3 or fewer dominoes, so the answer is 4.

Problem Statement

On the poker table, there are tea bags of N different flavors. The flavors are numbered from 1 through N, and there are A_i tea bags of flavor i (1 \leq i \leq N).

You will play a game using these tea bags. The game has a parameter called difficulty between 1 and A_1 + \dots + A_N, inclusive. A game of difficulty b proceeds as follows:

1. You declare an integer x. Here, it must satisfy b \leq x \leq A_1 + \dots + A_N.
2. The dealer chooses exactly x tea bags from among those on the table and gives them to you.
3. You check the flavors of the x tea bags you received, and choose b tea bags from them.
4. If all b tea bags you chose are of the same flavor, you win. Otherwise, you lose.

The dealer will do their best to make you lose.

You are given Q queries, so answer each of them. The j-th query is as follows:

• For a game of difficulty B_j, report the minimum integer x you must declare at the start to guarantee a win. If it is impossible to win, report -1 instead.

Constraints

• 1 \leq N \leq 3 \times 10^5
• 1 \leq Q \leq 3 \times 10^5
• 1 \leq A_i \leq 10^6 (1 \leq i \leq N)
• 1 \leq B_j \leq \min(10^6, A_1 + \dots + A_N) (1 \leq j \leq Q)
• All input values are integers.

Sample Input 1

4 5
4 1 8 4
1
8
5
2
10

Sample Output 1

1
17
14
5
-1

For the 1-st query, if you declare x=1, then no matter which 1 bag the dealer chooses, you can satisfy the winning condition by choosing appropriate 1 bag among them. Since you cannot choose an integer x less than 1, the answer is 1.

For the 2-nd query, if you declare x=17, then no matter which 17 bags the dealer chooses, you can satisfy the winning condition by choosing appropriate 8 bags among them. Conversely, if x < 17, the dealer can choose bags to prevent your victory. Thus, the answer is 17.

For the 3-rd query, if you declare x=14, then no matter which 14 bags the dealer chooses, you can satisfy the winning condition by choosing appropriate 5 bags among them. Conversely, if x < 14, the dealer can choose bags to prevent your victory. Thus, the answer is 14.

For the 4-th query, if you declare x=5, then no matter which 5 bags the dealer chooses, you can satisfy the winning condition by choosing appropriate 2 bags among them. Conversely, if x < 5, the dealer can choose bags to prevent your victory. Thus, the answer is 5.

For the 5-th query, no matter what x you declare, the dealer can choose bags to prevent your victory. Thus, print -1.

Sample Input 2

5 3
13 13 13 13 2
5
12
13

Sample Output 2

19
47
51

Problem Statement

Takahashi is having trouble with deciding a username for a service. Write a code to help him.

Find a string X that satisfies all of the following conditions:

• X is obtained by the following procedure:
  • Let S_1', S_2', \ldots,S_N' be a permutation of S_1, S_2, \ldots,S_N. Let X be the concatenation of S_1', (1 or more copies of _), S_2', (1 or more copies of _), \ldots, (1 or more copies of _), and S_N', in this order.
• The length of X is between 3 and 16, inclusive.
• X does not coincide with any of M strings T_1,T_2,\ldots,T_M.

If there is no X that satisfies all of the conditions, print -1 instead.

Constraints

• 1 \leq N \leq 8
• 0 \leq M \leq 10^5
• N and M are integers.
• 1 \leq |S_i| \leq 16
• N-1+\sum{|S_i|} \leq 16
• S_i \neq S_j if i \neq j.
• S_i is a string consisting of lowercase English letters.
• 3 \leq |T_i| \leq 16
• T_i \neq T_j if i \neq j.
• T_i is a string consisting of lowercase English letters and _.

Sample Input 1

1 1
chokudai
chokudai

Sample Output 1

-1

The only string that satisfies the first and second conditions is X= chokudai, but it coincides with T_1.
Thus, there is no X that satisfies all of the conditions, so -1 should be printed.

Sample Input 2

2 2
choku
dai
chokudai
choku_dai

Sample Output 2

dai_choku

Strings like choku__dai (which has two _'s between choku and dai) also satisfy all of the conditions.

Sample Input 3

2 2
chokudai
atcoder
chokudai_atcoder
atcoder_chokudai

Sample Output 3

-1

chokudai__atcoder and atcoder__chokudai (which have two _'s between chokudai and atcoder) have a length of 17, which violates the second condition.

Sample Input 4

4 4
ab
cd
ef
gh
hoge
fuga
____
_ab_cd_ef_gh_

Sample Output 4

ab__ef___cd_gh

The given T_i may contain a string that cannot be obtained by the procedure described in the first condition.

Problem Statement

There are N six-sided dice. The dice are numbered from 1 to N, and the numbers written on the faces of die i are A_{i,1},A_{i,2},\dots,A_{i,6}.

Now, all N dice will be rolled simultaneously. Find the expected value, modulo 998244353, of the maximum value among the numbers written on the face that comes up on each die.

For any die, the face that comes up when the die is rolled is chosen independently and uniformly at random.

Constraints

• 1\leq N \leq 10^5
• 1\leq A_{i,j} \leq 10^9
• All input values are integers.

Sample Input 1

2
1 1 4 4 4 4
1 1 1 3 3 3

Sample Output 1

332748121

Let x_i be the number written on the face that comes up on die i.

• Case x_1=1,x_2=1: Occurs with probability \frac{2}{6}\times\frac{3}{6}=\frac{1}{6}, and the maximum value among the numbers written on the faces that come up is 1.
• Case x_1=1,x_2=3: Occurs with probability \frac{2}{6}\times\frac{3}{6}=\frac{1}{6}, and the maximum value among the numbers written on the faces that come up is 3.
• Case x_1=4,x_2=1: Occurs with probability \frac{4}{6}\times\frac{3}{6}=\frac{1}{3}, and the maximum value among the numbers written on the faces that come up is 4.
• Case x_1=4,x_2=3: Occurs with probability \frac{4}{6}\times\frac{3}{6}=\frac{1}{3}, and the maximum value among the numbers written on the faces that come up is 4.

Thus, the expected value to be found is \frac{1}{6}\times 1 + \frac{1}{6}\times 3 + \frac{1}{3}\times 4 + \frac{1}{3}\times 4 = \frac{10}{3} \equiv 332748121 \pmod{998244353}.

Sample Input 2

2
1 1 1 1 1 1
2 2 2 2 2 2

Sample Output 2

2

The numbers written on the faces that come up on dice 1,2 are always 1,2, respectively, and their maximum value is always 2.

Sample Input 3

8
55 76 80 21 34 28
82 84 2 32 56 17
11 57 37 28 39 18
47 2 97 25 75 29
72 45 22 75 26 81
6 79 16 68 68 40
31 80 68 57 18 55
49 10 63 91 93 40

Sample Output 3

213725517

Problem Statement

Takahashi plans to participate in N AtCoder contests.

In the i-th contest (1 \leq i \leq N), if his rating is between L_i and R_i (inclusive), his rating increases by 1.

You are given Q queries in the following format:

• An integer X is given. Assuming that Takahashi's initial rating is X, determine his rating after participating in all N contests.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq L_i \leq R_i \leq 5 \times 10^5 (1 \leq i \leq N)
• 1 \leq Q \leq 3 \times 10^5
• For each query, 1 \leq X \leq 5 \times 10^5.
• All input values are integers.

Sample Input 1

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

Sample Output 1

6
6
8

For the 1st query, the rating changes as follows:

• In the 1st contest, the rating is between 1 and 5, so it increases by 1, becoming 4.
• In the 2nd contest, the rating is not between 1 and 3, so it remains 4.
• In the 3rd contest, the rating is between 3 and 6, so it increases by 1, becoming 5.
• In the 4th contest, the rating is not between 2 and 4, so it remains 5.
• In the 5th contest, the rating is between 4 and 7, so it increases by 1, becoming 6.

For the 2nd query, the rating increases in the 1st, 2nd, 3rd, and 5th contests, ending at 6.

For the 3rd query, the rating increases in the 1st, 3rd, and 5th contests, ending at 8.

Sample Input 2

10
1 1999
1 1999
1200 2399
1 1999
1 1999
1 1999
2000 500000
1 1999
1 1999
1600 2799
7
1
1995
2000
2399
500000
2799
1000

Sample Output 2

8
2002
2003
2402
500001
2800
1007

Sample Input 3

15
260522 414575
436426 479445
148772 190081
190629 433447
47202 203497
394325 407775
304784 463982
302156 468417
131932 235902
78537 395728
223857 330739
286918 329211
39679 238506
63340 186568
160016 361868
10
287940
296263
224593
101449
336991
390310
323355
177068
11431
8580

Sample Output 3

287946
296269
224599
101453
336997
390315
323363
177075
11431
8580