Problem Statement

Snuke has four cookies with deliciousness A, B, C, and D. He will choose one or more from those cookies and eat them. Is it possible that the sum of the deliciousness of the eaten cookies is equal to that of the remaining cookies?

Constraints

• All values in input are integers.
• 1 \leq A,B,C,D \leq 10^{8}

Sample Input 1

1 3 2 4

Sample Output 1

Yes

• If he eats the cookies with deliciousness 1 and 4, the sum of the deliciousness of the eaten cookies will be equal to that of the remaining cookies.

Sample Input 2

1 2 4 8

Sample Output 2

No

• Whatever choice he makes, the sum of the deliciousness of the eaten cookies will never be equal to that of the remaining cookies.

Problem Statement

Snuke had N cards numbered 1 through N. Each card has an integer written on it; written on Card i is a_i.

Snuke did the following procedure:

1. Let X and x be the maximum and minimum values written on Snuke's cards, respectively.
2. If X = x, terminate the procedure. Otherwise, replace each card on which X is written with a card on which X-x is written, then go back to step 1.

Under the constraints in this problem, it can be proved that the procedure will eventually terminate. Find the number written on all of Snuke's cards after the procedure.

Constraints

• All values in input are integers.
• 1 \leq N \leq 10^{5}
• 1 \leq a_i \leq 10^9

Sample Input 1

3
2 6 6

Sample Output 1

2

• At the beginning of the procedure, the numbers written on Snuke's cards are (2,6,6).
  • Since x=2 and X=6, he replaces each card on which 6 is written with a card on which 4 is written.
• Now, the numbers written on Snuke's cards are (2,4,4).
  • Since x=2 and X=4, he replaces each card on which 4 is written with a card on which 2 is written.
• Now, the numbers written on Snuke's cards are (2,2,2).
  • Since x=2 and X=2, he terminates the procedure.

Sample Input 2

15
546 3192 1932 630 2100 4116 3906 3234 1302 1806 3528 3780 252 1008 588

Sample Output 2

42

Problem Statement

There are N camels numbered 1 through N.

The weight of Camel i is w_i.

You will arrange the camels in a line and make them cross a bridge consisting of M parts.

Before they cross the bridge, you can choose their order in the line - it does not have to be Camel 1, 2, \ldots, N from front to back - and specify the distance between each adjacent pair of camels to be any non-negative real number. The camels will keep the specified distances between them while crossing the bridge.

The i-th part of the bridge has length l_i and weight capacity v_i. If the sum of the weights of camels inside a part (excluding the endpoints) exceeds v_i, the bridge will collapse.

Determine whether it is possible to make the camels cross the bridge without it collapsing. If it is possible, find the minimum possible distance between the first and last camels in the line in such a case.

It can be proved that the answer is always an integer, so print an integer.

Constraints

• All values in input are integers.
• 2 \leq N \leq 8
• 1 \leq M \leq 10^5
• 1 \leq w_i,l_i,v_i \leq 10^8

Sample Input 1

3 2
1 4 2
10 4
2 6

Sample Output 1

10

• It is possible to make the camels cross the bridge without it collapsing by, for example, arranging them in the order 1, 3, 2 from front to back, and setting the distances between them to be 0, 10.
  • For Part 1 of the bridge, there are moments when only Camel 1 and 3 are inside the part and moments when only Camel 2 is inside the part. In both cases, the sum of the weights of camels does not exceed 4 - the weight capacity of Part 1 - so there is no collapse.
  • For Part 2 of the bridge, there are moments when only Camel 1 and 3 are inside the part and moments when only Camel 2 is inside the part. In both cases, the sum of the weights of camels does not exceed 6 - the weight capacity of Part 2 - so there is no collapse.
• Note that the distance between two camels may be 0 and that camels on endpoints of a part are not considered to be inside the part.

Sample Input 2

2 1
12 345
1 1

Sample Output 2

-1

• Print -1 if the bridge will unavoidably collapse.

Sample Input 3

8 1
1 1 1 1 1 1 1 1
100000000 1

Sample Output 3

700000000

Sample Input 4

8 20
57 806 244 349 608 849 513 857
778 993
939 864
152 984
308 975
46 860
123 956
21 950
850 876
441 899
249 949
387 918
34 965
536 900
875 889
264 886
583 919
88 954
845 869
208 963
511 975

Sample Output 4

3802

Problem Statement

We have N bags numbered 1 through N and N dishes numbered 1 through N. Bag i contains a_i coins, and each dish has nothing on it initially.

Taro the first and Jiro the second will play a game against each other. They will alternately take turns, with Taro the first going first. In each player's turn, the player can make one of the following two moves:

1. When one or more bags contain coin(s): Choose one bag that contains coin(s) and one dish, then move all coins in the chosen bag onto the chosen dish. (The chosen dish may already have coins on it, or not.)
2. When no bag contains coins: Choose one dish with coin(s) on it, then remove one or more coins from the chosen dish.

The player who first becomes unable to make a move loses. Determine the winner of the game when the two players play optimally.

You are given T test cases. Solve each of them.

Constraints

• All values in input are integers.
• 1 \leq T \leq 10^5
• 1 \leq N \leq 10^{5}
• 1 \leq a_i \leq 10^9
• In one input file, the sum of N does not exceed 2 \times 10^5.

Sample Input 1

3
1
10
2
1 2
21
476523737 103976339 266993 706803678 802362985 892644371 953855359 196462821 817301757 409460796 773943961 488763959 405483423 616934516 710762957 239829390 55474813 818352359 312280585 185800870 255245162

Sample Output 1

Second
First
Second

• In test case 1, Jiro the second wins. Below is one sequence of moves that results in Jiro's win:
  • In Taro the first's turn, he can only choose Bag 1 and move the coins onto Dish 1.
  • In Jiro the second's turn, he can choose Dish 1 and remove all coins from it, making Taro fail to make a move and lose.
• Note that when there is a bag that contains coin(s), a player can only make a move in which he chooses a bag that contains coin(s) and moves the coin(s) onto a dish.
• Similarly, note that when there is no bag that contains coin(s), a player can only make a move in which he chooses a dish and removes one or more coins.

Problem Statement

Given is an undirected graph G consisting of N vertices numbered 1 through N and M edges numbered 1 through M. Edge i connects Vertex a_i and Vertex b_i bidirectionally.

G is said to be a good graph when both of the conditions below are satisfied. It is guaranteed that G is initially a good graph.

• Vertex 1 and Vertex N are not connected.
• There are no self-loops and no multi-edges.

Taro the first and Jiro the second will play a game against each other. They will alternately take turns, with Taro the first going first. In each player's turn, the player can do the following operation:

• Operation: Choose vertices u and v, then add to G an edge connecting u and v bidirectionally.

The player whose addition of an edge results in G being no longer a good graph loses. Determine the winner of the game when the two players play optimally.

You are given T test cases. Solve each of them.

Constraints

• All values in input are integers.
• 1 \leq T \leq 10^5
• 2 \leq N \leq 10^{5}
• 0 \leq M \leq \min(N(N-1)/2,10^{5})
• 1 \leq a_i,b_i \leq N
• The given graph is a good graph.
• In one input file, the sum of N and that of M do not exceed 2 \times 10^5.

Sample Input 1

3
3 0
6 2
1 2
2 3
15 10
12 14
8 3
10 1
14 6
12 6
1 9
13 1
2 5
3 9
7 2

Sample Output 1

First
Second
First

• In test case 1, Taro the first wins. Below is one sequence of moves that results in Taro's win:
  • In Taro the first's turn, he adds an edge connecting Vertex 1 and 2, after which the graph is still good.
  • Then, whichever two vertices Jiro the second would choose to connect with an edge, the graph would no longer be good.
  • Thus, Taro wins.

Problem Statement

Given is an undirected graph G consisting of N vertices numbered 1 through N and M edges numbered 1 through M. It is guaranteed that G is connected and contains no self-loops and no multi-edges. Edge i connects Vertex a_i and Vertex b_i bidirectionally. Each edge can be painted red or blue. Initially, every edge is painted red.

Consider making a new graph G^{\prime} by removing zero or more edges from G. There are 2^M graphs that G^{\prime} can be. Among them, find the number of good graphs defined below, modulo 998244353.

G^{\prime} is said to be a good graph when both of the following conditions are satisfied:

• G^{\prime} is connected.
• It is possible to make all edges blue by doing the following operation zero or more times.
  • Choose one vertex and change the color of every edge incident to that vertex, that is, red to blue and vice versa.

Constraints

• All values in input are integers.
• 1 \leq N \leq 17
• N-1 \leq M \leq N(N-1)/2
• G is connected and has no self-loops and no multi-edges.

Sample Input 1

3 2
1 2
2 3

Sample Output 1

1

• The conditions are satisfied only if neither Edge 1 nor Edge 2 is removed.
  • In this case, we can make all edges blue by, for example, doing the operation for Vertex 2.
• Otherwise, the graph gets disconnected and thus does not satisfy the condition.

Sample Input 2

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

Sample Output 2

19

Sample Input 3

17 50
16 17
10 9
16 10
5 17
6 15
5 9
15 11
16 1
8 13
6 17
15 3
16 15
11 3
7 6
1 4
11 13
10 6
10 12
3 16
7 3
16 5
13 3
12 13
7 11
3 12
13 10
1 12
9 15
11 14
4 6
13 2
6 1
15 2
1 14
15 17
2 11
14 13
16 9
16 8
8 17
17 12
1 11
6 12
17 2
8 1
14 6
9 7
11 10
5 14
17 7

Sample Output 3

90625632

• Be sure to find the count modulo 998244353.