Problem Statement

Takahashi is playing a game. This game has eight worlds, and each world has eight stages. The stages have an order, and the first stage is the 1st stage in the 1st world. The next stage after the j-th stage (1\le j\le 8) in the i-th world (1\le i\le 8) is as follows:

• When j\lt8, the next stage is the (j+1)-th stage in the i-th world.
• When i\lt8,j=8, the next stage is the 1st stage in the (i+1)-th world.
• When i=8,j=8, there is no next stage. This stage is the last stage.

The name of the j-th stage (1\le j\le 8) in the i-th world (1\le i\le 8) is i-j. For example, the name of the first stage is 1-1, and the name of the last stage is 8-8.

Given the stage name S of the stage Takahashi is currently playing, output the stage name of the next stage.

Constraints

• S is the stage name of one of the stages.
• S is not 8-8.

Sample Input 1

4-2

Sample Output 1

4-3

The next stage after the 2nd stage in the 4th world is the 3rd stage in the same world.

Sample Input 2

1-8

Sample Output 2

2-1

1-8 is the last stage in the 1st world, so the next stage is the 1st stage in the 2nd world.

Sample Input 3

3-3

Sample Output 3

3-4

Problem Statement

There is a grid with H rows and W columns. Let (i,j) denote the cell at the i-th row (1\le i\le H) from the top and the j-th column (1\le j\le W) from the left.

Each cell is painted with one color, white or black. The color painted on the cells is represented by H strings S _ 1,S _ 2,\ldots,S _ H. When the j-th character (1\le j\le W) of S _ i\ (1\le i\le H) is ., cell (i,j) is painted white, and when the j-th character (1\le j\le W) of S _ i\ (1\le i\le H) is #, cell (i,j) is painted black.

Determine whether the grid satisfies the following condition:

• For every black cell, the number of horizontally or vertically adjacent cells that are painted black is 2 or 4.

Here, cells (i,j)\ (1\le i\le H,1\le j\le W) and (k,l)\ (1\le k\le H,1\le l\le W) are horizontally or vertically adjacent if and only if |i-k|+|j-l|=1.

Constraints

• 1\le H\le 20
• 1\le W\le 20
• H and W are integers.
• S _ i is a string of length W consisting of . and # (1\le i\le H).

Sample Input 1

8 7
.######
##....#
#.###.#
#.#.#.#
#.#.#.#
#.#####
#...#..
#####..

Sample Output 1

Yes

For example, cell (6,3) is painted black, and among the adjacent cells (5,3),(6,2),(6,4),(7,3), cells (5,3) and (6,4) are painted black, which is 2 cells, so it satisfies the condition.

Every other black cell also satisfies the condition, so output Yes.

Sample Input 2

1 2
##

Sample Output 2

No

Cell (1,1) is painted black, but it has only one adjacent cell, so it does not satisfy the condition.

Therefore, output No.

Sample Input 3

4 3
...
...
...
...

Sample Output 3

Yes

There are no black cells, so the condition is satisfied.

Therefore, output Yes.

Sample Input 4

15 18
##.###..##.##..##.
##.#.##.##.##.####
...##.#.......####
###.###....###.##.
#.##.......#.#....
#..#.##.##.#.#....
#.########.####.##
#.##.##.#....##.##
#......##.........
##.##..#..##..####
.#.#####..#####..#
.#..#...##.#.....#
.#..#.####.#.....#
.##.#.#.#..##..###
..###.###...####..

Sample Output 4

Yes

Problem Statement

Takahashi has some letters. Each letter he has is A, B, or C. Initially, he has n _ A letters A, n _ B letters B, and n _ C letters C.

He can hold one contest by using one letter A, one letter C, and additionally any one letter, for a total of three letters. Specifically, he can hold AAC by using two letters A and one letter C, ABC by using one letter each of A, B, and C, and ACC by using one letter A and two letters C.

He wants to hold as many contests as possible using the letters he currently has. Find the maximum number of contests he can hold.

T test cases are given, so report the answer for each of them.

Constraints

• 1\le T\le2\times10 ^ 5
• For each test case,
  • 0\le n _ A\le10 ^ 9
  • 0\le n _ B\le10 ^ 9
  • 0\le n _ C\le10 ^ 9
• All input values are integers.

Sample Input 1

5
3 1 2
100 0 0
1000000 1000000 1000000
31 41 59
1000000000 10000 1

Sample Output 1

2
0
1000000
31
1

In the first test case, he can hold AAC once and ABC once, for a total of two contests. Therefore, output 2 on the first line.

Problem Statement

Let N be a positive integer. Define the imbalance of a sequence A=(A_1, A_2, \dots, A_{2^N}) of non-negative integers of length 2^N as the non-negative integer value obtained by the following operation:

• Initially, set X=0.
• Perform the following series of operations N times:
  • Update X to \max(X, \max(A) - \min(A)), where \max(A) and \min(A) denote the maximum and minimum values of sequence A, respectively.
  • Form a new sequence of half the length by pairing elements from the beginning two by two and arranging their sums. That is, set A \gets (A_1 + A_2, A_3 + A_4, \dots, A_{\vert A \vert - 1} + A_{\vert A \vert}).
• The final value of X is the imbalance.

For example, when N=2, A=(6, 8, 3, 5), the imbalance is 6 through the following steps:

• Initially, X=0.
• The first series of operations is as follows:
  • Update X to \max(X, \max(A) - \min(A)) = \max(0, 8 - 3) = 5.
  • Set A to (6+8, 3+5) = (14, 8).
• The second series of operations is as follows:
  • Update X to \max(X, \max(A) - \min(A)) = \max(5, 14 - 8) = 6.
  • Set A to (14 + 8) = (22).
• Finally, X=6.

You are given a non-negative integer K. Among all sequences of non-negative integers of length 2^N with sum K, construct a sequence that minimizes the imbalance.

Constraints

• 1 \leq N \leq 20
• 0 \leq K \leq 10^9
• N and K are integers.

Sample Input 1

1 11

Sample Output 1

1
5 6

(5, 6) is a sequence with imbalance 1, which is the minimum imbalance among sequences satisfying the condition.

Sample Input 2

3 56

Sample Output 2

0
7 7 7 7 7 7 7 7

Problem Statement

There are N points on a two-dimensional plane. N is odd. The i-th point is at (x_i, y_i). All point coordinates are distinct.
Determine whether there exists a line passing through more than half of the N points, and if so, output it.
For any input satisfying the constraints, if a line satisfying the condition exists, it can be expressed as ax+by+c=0 using integers a,b,c with -10^{18} \leq a,b,c \leq 10^{18} (where (a,b,c) \neq (0,0,0)). Output these a,b,c.

Constraints

• 3 \leq N \leq 5 \times 10^5
• N is odd.
• -10^8 \leq x_i \leq 10^8
• -10^8 \leq y_i \leq 10^8
• If i \neq j, then (x_i, y_i) \neq (x_j, y_j).
• All input values are integers.

Sample Input 1

3
1 1
3 2
2 4

Sample Output 1

Yes
2 1 -8

The line 2x+y-8=0 passes through the 2nd and 3rd points, so it satisfies the condition.

Sample Input 2

5
5 2
1 3
2 6
4 4
5 4

Sample Output 2

No

No line satisfying the condition exists.

Sample Input 3

11
-9374372 85232388
-60705467 86198234
-7475320 80628487
98066347 -23868213
-12177678 85284287
30535572 -35358356
51324557 22410787
28854279 44658587
-28804873 82911971
65052073 8819187
-67744430 68365758

Sample Output 3

Yes
4655800 4702358 -344340416016346

Problem Statement

There is a connected undirected graph with N vertices and M edges. The vertices are numbered vertex 1, vertex 2,\ldots, vertex N, and the i-th edge (1\le i\le M) connects vertices u _ i and v _ i.

For i=1,2,\ldots,N, solve the following problem:

Initially, Takahashi's weight is 0.

He travels by car to visit vertex 1 and moves toward vertex i. When he visits vertex v\ (1\le v\le N), his weight increases by W _ v.

The car he is riding can move along the edges. When he passes through an edge, letting X be his weight at that time, the car consumes X fuel.

Find the minimum amount of fuel consumed for him to reach vertex i.

Constraints

• 1\le N\le5000
• 1\le M\le5000
• 1\le W _ i\le10 ^ 9\ (1\le i\le N)
• 1\le u _ i\le v _ i\le N\ (1\le i\le M)
• The given graph is connected.
• All input values are integers.

Sample Input 1

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

Sample Output 1

0
3
3
7
10

The given graph is as follows:

For example, Takahashi can reach vertex 5 by visiting vertex 1 and then acting as follows:

• He visits vertex 1. His weight increases by 3, becoming 3.
• He consumes 3 fuel to move to vertex 3. His weight increases by 4, becoming 7.
• He consumes 7 fuel to move to vertex 5. His weight increases by 5, becoming 12.

By acting this way, he can reach vertex 5 by consuming 10 fuel. It is impossible to reduce the fuel consumption to 9 or less, so output 10 on the 5th line.

Sample Input 2

5 4
1000000000 1000000000 1000000000 1000000000 1000000000
1 2
2 3
3 4
4 5

Sample Output 2

0
1000000000
3000000000
6000000000
10000000000

Note that the answer may exceed 2 ^ {32}.

Sample Input 3

10 20
74931 58277 33783 91022 53003 11085 65924 63548 78622 77307
1 8
3 6
5 10
4 6
1 3
1 7
2 6
7 10
8 9
3 4
4 4
4 6
6 6
5 10
1 7
4 5
1 2
3 7
2 3
5 8

Sample Output 3

0
74931
74931
183645
213410
183645
74931
74931
213410
215786

Problem Statement

You are given positive integers A, B, C, N.
Solve Problems 1 and 2. (The differences between the problems are indicated in bold.)

Problem 1

There are N balls. The balls are indistinguishable from each other. Also, there are boxes 1, 2, and 3.
Find the number, modulo 998244353, of ways to put all balls into the boxes satisfying the following conditions.

• The number of balls in box 1 is a multiple of A.
• The number of balls in box 2 is a multiple of B.
• The number of balls in box 3 is a multiple of C.

Here, two ways of putting balls are counted separately when there exists a box where the number of balls differs between the two ways.

Problem 2

There are N balls numbered from 1 to N. The balls are distinguishable from each other. Also, there are boxes 1, 2, and 3.
Find the number, modulo 998244353, of ways to put all balls into the boxes satisfying the following conditions.

• The number of balls in box 1 is a multiple of A.
• The number of balls in box 2 is a multiple of B.
• The number of balls in box 3 is a multiple of C.

Here, two ways of putting balls are counted separately when there exists a ball whose box differs between the two ways.

Constraints

• 1 \leq N \leq 3 \times 10^5
• 1 \leq A \leq 3 \times 10^5
• 1 \leq B \leq 3 \times 10^5
• 1 \leq C \leq 3 \times 10^5
• All input values are integers.

Sample Input 1

3 1 2 3

Sample Output 1

3
5

In Problem 1, the ways of putting balls that satisfy the condition are the following three ways:

• Put 3 balls in box 1.
• Put 1 ball in box 1 and 2 balls in box 2.
• Put 3 balls in box 3.

In Problem 2, the ways of putting balls that satisfy the condition are the following five ways:

• Put balls 1,2,3 in box 1.
• Put ball 1 in box 1 and balls 2,3 in box 2.
• Put ball 2 in box 1 and balls 1,3 in box 2.
• Put ball 3 in box 1 and balls 1,2 in box 2.
• Put balls 1,2,3 in box 3.

Sample Input 2

1234 56 7 89

Sample Output 2

15
535248725

Sample Input 3

300000 6 490 420

Sample Output 3

73339
760083042

Sample Input 4

12345 67 89 123456

Sample Output 4

2
150951502