Problem Statement

You are given an integer sequence of length N: A = (A_1,A_2,\ldots,A_N).

Determine whether there is a place in A where the same element appears three or more times in a row.

More formally, determine whether there exists an integer i with 1 \le i \le N-2 such that A_i = A_{i+1} = A_{i+2}.

Constraints

• 3 \le N \le 100
• 1 \le A_i \le 100
• All input values are integers.

Sample Input 1

5
1 4 4 4 2

Sample Output 1

Yes

We have A=(1,4,4,4,2). There is a place where 4 appears three times in a row, so print Yes.

Sample Input 2

6
2 4 4 2 2 4

Sample Output 2

No

We have A=(2,4,4,2,2,4). There is no place where the same element appears three or more times in a row, so print No.

Sample Input 3

8
1 4 2 5 7 7 7 2

Sample Output 3

Yes

Sample Input 4

10
1 2 3 4 5 6 7 8 9 10

Sample Output 4

No

Sample Input 5

13
1 1 1 1 1 1 1 1 1 1 1 1 1

Sample Output 5

Yes

Problem Statement

There is a stack of 100 cards, each labeled with the integer 0.

Process Q queries. Each query is of one of the following:

• Type 1: Place a card labeled with an integer x on top of the stack.
• Type 2: Remove the top card of the stack and output the integer written on that removed card. Under the constraints of this problem, the stack always has at least one card.

Constraints

• 1 \le Q \le 100
• 1 \le x \le 100
• There is at least one query of type 2.
• All input values are integers.

Sample Input 1

6
2
1 4
1 3
2
2
2

Sample Output 1

0
3
4
0

After processing each query, the stack is as follows:

• Remove the top card of the stack. The integer on the removed card is 0, so output 0.
  • The stack then has 99 cards labeled with 0.
• Add a card labeled 4 on top.
  • The stack then has 1 card labeled 4, and 99 cards labeled 0, from top to bottom.
• Add a card labeled 3 on top.
  • The stack then has 1 card labeled 3, 1 card labeled 4, and 99 cards labeled 0, from top to bottom.
• Remove the top card. The integer on that card is 3, so output 3.
  • The stack then has 1 card labeled 4, and 99 cards labeled 0, from top to bottom.
• Remove the top card. The integer on that card is 4, so output 4.
  • The stack then has 99 cards labeled 0.
• Remove the top card. The integer on that card is 0, so output 0.
  • The stack then has 98 cards labeled 0.

Sample Input 2

5
2
2
2
2
2

Sample Output 2

0
0
0
0
0

Problem Statement

There are N black balls and M white balls.
Each ball has a value. The value of the i-th black ball (1 \le i \le N) is B_i, and the value of the j-th white ball (1 \le j \le M) is W_j.

Choose zero or more balls so that the number of black balls chosen is at least the number of white balls chosen. Among all such choices, find the maximum possible sum of the values of the chosen balls.

Constraints

• 1 \leq N,M \leq 2\times 10^5
• -10^9 \leq B_i, W_j \leq 10^9
• All input values are integers.

Sample Input 1

4 3
8 5 -1 3
3 -2 -4

Sample Output 1

19

If you choose the 1st, 2nd, and 4th black balls, and the 1st white ball, the sum of their values is 8+5+3+3=19, which is the maximum.

Sample Input 2

4 3
5 -10 -2 -5
8 1 4

Sample Output 2

15

If you choose the 1st and 3rd black balls, and the 1st and 3rd white balls, the sum of their values is 5+(-2)+8+4=15, which is the maximum.

Sample Input 3

3 5
-36 -33 -31
12 12 28 24 27

Sample Output 3

0

It is possible to choose no balls.

Problem Statement

You are given a simple connected undirected graph with N vertices numbered 1 through N and M edges numbered 1 through M. Edge i connects vertices u_i and v_i, and has a label w_i.

Among all simple paths (paths that do not pass through the same vertex more than once) from vertex 1 to vertex N, find the minimum XOR of the labels of the edges on the path.

Constraints

• 2 \leq N \leq 10
• N-1 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq u_i < v_i \leq N
• 0 \leq w_i < 2^{60}
• The given graph is a simple connected undirected graph.
• All input values are integers.

Sample Input 1

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

Sample Output 1

3

There are two simple paths from vertex 1 to vertex 4:

• 1 \to 2 \to 4
• 1 \to 3 \to 4

The XOR of the labels on the edges of the first path is 6, and that of the second path is 3. Therefore, the answer is 3.

Sample Input 2

4 3
1 2 1
2 3 2
3 4 4

Sample Output 2

7

Sample Input 3

7 10
1 2 726259430069220777
1 4 988687862609183408
1 5 298079271598409137
1 6 920499328385871537
1 7 763940148194103497
2 4 382710956291350101
3 4 770341659133285654
3 5 422036395078103425
3 6 472678770470637382
5 7 938201660808593198

Sample Output 3

186751192333709144

Problem Statement

You are given integers N, M and three integer sequences of length M: X = (X_1, X_2, \ldots, X_M), Y = (Y_1, Y_2, \ldots, Y_M), and Z = (Z_1, Z_2, \ldots, Z_M). It is guaranteed that all elements of X and Y are between 1 and N, inclusive.

We call a length-N sequence of non-negative integers A = (A_1, A_2, \ldots, A_N) a good sequence if and only if it satisfies the following condition:

• For every integer i with 1 \le i \le M, the XOR of A_{X_i} and A_{Y_i} is Z_i.

Determine whether a good sequence A=(A_1,A_2,\ldots,A_N) exists, and if it exists, find one good sequence that minimizes the sum of its elements \displaystyle \sum_{i=1}^N A_i.

Constraints

• 1 \le N \le 2\times 10^5
• 0 \le M \le 10^5
• 1 \le X_i, Y_i \le N
• 0 \le Z_i \le 10^9
• All input values are integers.

Sample Input 1

3 2
1 3 4
1 2 3

Sample Output 1

0 3 4

A=(0,3,4) is a good sequence because A_1 \oplus A_2 = 3 and A_1 \oplus A_3 = 4.

Other good sequences include A=(1,2,5) and A=(7,4,3), but A=(0,3,4) has the smallest sum among all good sequences.

Sample Input 2

3 3
1 3 4
1 2 3
2 3 5

Sample Output 2

-1

No good sequence exists, so print -1.

Sample Input 3

5 8
4 2 4
2 3 11
3 4 15
4 5 6
3 2 11
3 3 0
3 1 9
3 4 15

Sample Output 3

0 2 9 6 0

Problem Statement

You are given integers N, M and a length-N sequence of non-negative integers A = (A_1, A_2, \ldots, A_N).

For k = 0, 1, \ldots, M-1, solve the following problem:

Define an integer sequence B = (B_1, B_2, \ldots, B_N) so that B_i is the remainder of A_i + k when divided by M. Find the inversion number in B.

Constraints

• 1 \le N,M \le 2\times 10^5
• 0 \le A_i < M
• All input values are integers.

Sample Input 1

3 3
2 1 0

Sample Output 1

3
1
1

• For k=0: B=(2, 1, 0). The inversion number is 3.
• For k=1: B=(0, 2, 1). The inversion number is 1.
• For k=2: B=(1, 0, 2). The inversion number is 1.

Sample Input 2

5 6
5 3 5 0 1

Sample Output 2

7
3
3
1
1
5

Sample Input 3

7 7
0 1 2 3 4 5 6

Sample Output 3

0
6
10
12
12
10
6

Problem Statement

There is a H \times W grid, and each cell contains 0 or 1. The cell at the i-th row from the top and the j-th column from the left contains an integer A_{i,j}.

You can perform the following two operations any number of times in any order:

• Operation X: Choose an integer x (1 \leq x \leq H). For every integer 1 \leq y \leq W, replace A_{x,y} with 1 - A_{x,y}.
• Operation Y: Choose an integer y (1 \leq y \leq W). For every integer 1 \leq x \leq H, replace A_{x,y} with 1 - A_{x,y}.

Find the minimum possible value of \displaystyle \sum_{x=1}^H\sum_{y=1}^W A_{x,y} after the process.

Constraints

• 1 \leq H \leq 2\times 10^5
• 1 \leq W \leq 18
• H and W are integers.
• A_{i,1}A_{i,2}\ldots A_{i,W} is a length-W string consisting of 0 and 1.

Sample Input 1

3 3
100
010
110

Sample Output 1

2

By performing the following operations, the grid changes as shown below, and you get \displaystyle \sum_{x=1}^H\sum_{y=1}^W A_{x,y} = 2.

1. Operation Y with y=1
2. Operation X with x=2

It is impossible to make \displaystyle \sum_{x=1}^H\sum_{y=1}^W A_{x,y} \leq 1, so the answer is 2.

Sample Input 2

3 4
1111
1111
1111

Sample Output 2

0

Sample Input 3

10 5
10000
00111
11000
01000
10110
01110
10101
00100
00100
10001

Sample Output 3

13