Problem Statement

DEGwer's doctoral dissertation consists of N pages. Currently, there are K typos in this doctoral dissertation, and the i-th typo (i = 1, \ldots, K) is on page A_i.

To submit the doctoral dissertation, it is necessary to correct the typos so that no consecutive T pages contain multiple typos. Please help busy DEGwer, who is preparing this contest, by determining the minimum number of typos that need to be corrected in order to submit the doctoral dissertation.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq 2 \times 10^5
• 1 \leq T \leq N
• 1 \leq A_i \leq N \ \ (1 \leq i \leq K)

Sample Input 1

5 4 3
1 2 4 5

Sample Output 1

2

DEGwer's doctoral dissertation consists of 5 pages, with one typo each on the 1st, 2nd, 4th, and 5th pages.

For example, if the typos on the 1st and 4th pages are corrected, then no consecutive 3 pages will have multiple typos. On the other hand, it can also be confirmed that it is impossible to meet this condition by correcting only one typo. Therefore, output 2 as the minimum number of typos to be corrected.

Sample Input 2

4 8 2
1 1 1 1 1 4 2 2

Sample Output 2

6

There may also be multiple typos on a single page.

Sample Input 3

5 2 3
4 1

Sample Output 3

0

There may be no need to correct any typos.

Problem Statement

This is an interactive problem. Because the judge program (interactor) requires around 1 second in the worst case, the time limit is set to be longer.

You have eventually reached the castle of Great Satan DEGwer after 10-year journey. The entrance of the castle is a dungeon, which cannot avoid for arriving at DEGwer.

The dungeon is of form a grid with H rows and W columns. Each of H \times W squares is a room, and there is a door between any pair of adjacent rooms. In addition, there is an entrance door on the left side of each room located in the left-most column, and there is an exit door on the right side of each room located in the right-most column.

Now, all the door are unfixed. You want to let the dungeon such that some open exit door can be reached from some open entrance door by repeatedly passing through open doors, and DEGwer wants to prevent your objective. For their own objectives, you and DEGwer alternately use the following magics.

• Your magic: Choose any unfixed door, fix it as open (passable).
• DEGwer's magic: Choose any unfixed door, fix it as closed (impassable).

You are given the size (H, W) of the dungeon and who uses the magic first. Determine whether your objective is achievable or not when you and DEGwer do their best. In addition, if your objective is achievable, indicate interactively one possible way (your magics) to do so.

Constraints

• 1 \leq H \leq 20
• 1 \leq W \leq 20
• \textrm{move} is either First or Second, where First means that you use the magic first, and Second means that DEGwer uses the magic first.

Sample Input 1

1 1 First

Sample Output 1

No

In this case, the dungeon consists of only one room, whose left side has a unique entrance door and right side has a unique exit door. For your objective, you have to fix both doors as open, but it cannot be done even if you use the magic first. Thus, your objective is not achievable.

Sample Input 2

2 1 First

Sample Output 2

Yes
...

In this case, as shown in below, the dungeon consists of two vertically adjacent rooms, there is a unique vertically passable door between them, and the left and right sides of both rooms have two entrance and exit doors, respectively, in total.

| |
 -
| |

You use the magic first, and suppose that you choose the unique vertically passable door - 1 1. Then, no matter how DEGwer will choose doors, you can choose one from the remaining two entrance doors and one from the remaining two exit doors, which achieve your objective because the two rooms became connected by your first magic.

The following is an example of interactive inputs and outputs.

Sample Input 3

2 1 Second

Sample Output 3

No

The dungeon is the same as above, but your objective is not achievable as DEGwer uses the magic first. For example, if DEGwer fixes the unique vertically passable door (that you choose first in Sample 2) as closed, then the situation is just like two parallel copies of Sample 1, in which your objective is not achievable even if you use the magic first.

Problem Statement

Find the number of h \times w binary matrices which satisfy both of the following conditions modulo M:

• When each row is interpreted as a string of length w, they are sorted in lexicographical order in the row direction.
• When each column is interpreted as a string of length h, they are sorted in lexicographical order in the column direction.

Given integers H, W in the input, find the answer for all pairs of integers h, w that satisfy 1 \le h \le H, 1 \le w \le W.

Constraints

• 1 \le H \le 21
• 1 \le W \le 100
• 2 \le M \le 10^9

Sample Input 1

2 3 5201314

Sample Output 1

2 3 4
3 7 14

For example, in the case of (h, w) = (2, 3), there are 14 matrices that satisfy the conditions of the problem statement, as shown below:

000 000 000 000 001 001 001 001 001 011 011 011 011 111
000 001 011 111 001 010 011 110 111 011 100 101 111 111

Sample Input 2

10 8 1000000000

Sample Output 2

2 3 4 5 6 7 8 9
3 7 14 25 41 63 92 129
4 14 45 130 336 785 1682 3351
5 25 130 650 2942 11819 42305 136564
6 41 336 2942 24520 183010 1202234 6979061
7 63 785 11819 183010 2625117 33345183 371484319
8 92 1682 42305 1202234 33345183 836488618 470742266
9 129 3351 136564 6979061 371484319 470742266 230288201
10 175 6280 402910 36211867 651371519 194085968 670171373
11 231 11176 1099694 170079565 17940222 26957098 939510047

Sample Input 3

5 5 2

Sample Output 3

0 1 0 1 0
1 1 0 1 1
0 0 1 0 0
1 1 0 0 0
0 1 0 0 0

Problem Statement

You have a pair of integer sequences A=(A_1, A_2, \dots, A_N), B=(B_1, B_2, \dots, B_N). Initially A_i=B_i=0 holds for all i = 1, 2, \dots, N.

You will perform the following operation M times.

• Operation: Choose two integers i, j\ (1 \le i, j \le N) and increment A_i and B_j by 1.

Here, out of the M operations, the number of operations in which i=j holds must be exactly X.

Find the number, modulo 998244353, of pairs of integer sequences that A, B can be after the M operations.

Constraints

• 2 \leq N \leq 3000
• 0 \leq X \leq M \le 3000
• All input values are integers.

Sample Input 1

3 1 1

Sample Output 1

3

The following 3 pairs are possible.

• A=(1,0,0), \ B=(1,0,0)
• A=(0,1,0), \ B=(0,1,0)
• A=(0,0,1), \ B=(0,0,1)

Sample Input 2

3 1 0

Sample Output 2

6

The following 6 pairs are possible.

• A=(1,0,0), \ B=(0,1,0)
• A=(1,0,0), \ B=(0,0,1)
• A=(0,1,0), \ B=(1,0,0)
• A=(0,1,0), \ B=(0,0,1)
• A=(0,0,1), \ B=(1,0,0)
• A=(0,0,1), \ B=(0,1,0)

Sample Input 3

4 4 2

Sample Output 3

643

The followings are examples of possible pairs.

• A=(1,1,1,1), \ B=(1,1,1,1)
• A=(1,0,0,3), \ B=(0,1,0,3)

Sample Input 4

314 1592 653

Sample Output 4

755768689

Problem Statement

You are given a string S consisting of lowercase letters. For each contiguous substring of S (there are |S|(|S|+1)/2 such substrings), solve the following problem, and compute the sum of the answers.

Problem: You are given a string T consisting of lowercase letters. Compute the minimum possible length of a string that can be obtained from T by repeatedly applying the following operation an arbitrary number of times.

• Take a prefix of T that is a palindrome of odd length. Let the length be 2k+1. Remove the first k letters of T.

Constraints

• 1\leq |S|\leq 10^6
• S consists of lowercase letters.

Sample Input 1

abab

Sample Output 1

16

If T is a or b, the answer is 1.

If T is ab or ba, the answer is 2.

If T is aba or bab, applying the operation with k=1 once is optimal, and the answer is 2.

If T is abab, applying the operation with k=1 twice is optimal, and the answer is 2.

Therefore, the whole answer is 1\times 4 + 2\times 3 + 2\times 2 + 2\times 1 = 16.

Sample Input 2

abacaba

Sample Output 2

67

Sample Input 3

tabatadebatabata

Sample Output 3

739

Problem Statement

You are given positive integers N, M, K, and a sequence of K positive integers c=(c_1, c_2, \dots, c_K).

A multiset S consisting of N positive integers less than or equal to M is called good, if there exists at least one sequence of K multisets (S_1, S_2, \dots, S_K) satisfying the following conditions.

• None of S_1, S_2, \dots, S_K is empty.
• The median of S_i equals to c_i, for all i=1, 2, \dots, K.
• S_1, S_2, \dots, S_K have exactly N elements in total. A multiset consisting of those N elements coincides with S.

Note that we define the median of a multiset T with n\ (\geq 1) elements as the \lceil n / 2 \rceil-th element of T in ascending order. For example, the median of T=\lbrace 1, 2, 3, 4 \rbrace is 2, and that of T=\lbrace 1, 3, 5, 7, 7 \rbrace is 5.

Find the number of good multisets modulo 998244353.

Constraints

• 1 \leq N, M \leq 10^7
• 1 \leq K \leq \min(2 \times 10^5, N)
• 1 \leq c_i \leq M
• All input values are integers.

Sample Input 1

8 5 3
4 1 5

Sample Output 1

105

For example, S=\lbrace 1,1,1,2,3,4,5,5 \rbrace is a good multiset because there exists (S_1, S_2, S_3) satisfying the conditions as follows.

• S_1 = \lbrace 1, \mathbf{4}, 5 \rbrace
• S_2 = \lbrace 1, \mathbf{1}, 2, 3 \rbrace
• S_3 = \lbrace \mathbf{5} \rbrace

Sample Input 2

10000000 2 2
1 2

Sample Output 2

9999999

Sample Input 3

30 10 5
3 1 4 1 5

Sample Output 3

38446044

Problem Statement

For a three-dimensional convex polytope P, the net of it is the set of (possibly overlapping) polygons satisfying the following.

• Each polygon corresponds one-to-one with a face of P.
• P can be constructed by repeating the operation of folding along its edges.

Here, folding along an edge is the following operation:

• Choose an edge, the removal of which would make the current figure disconnected. Use the line defined by this edge as the axis of rotation and rotate the entire part of the current figure that lies on one side of this edge by any angle (in three dimensions). If necessary, vertices or edges that coincide exactly in coordinates are identified.

Similarly, the net of the net of P is the set of line segments satisfying the following.

• Each edge corresponds one-to one with an edge of the net of P.
• The net of P can be constructed by repeating the operation of folding along its vertices.

Here, folding along a vertex is the following operation:

• Choose a vertex, the removal of which would make the current figure disconnected. Use this vertex as the center of rotation and rotate the entire part of the current figure that lies on some side of this vertex by any angle (in two dimentions). If necessary, vertices that coincide exactly in coordinates are identified.

You are given N points on the unit sphere such that no four of these are on the same plain. The coordinate of i-th point is given by (x_i,y_i,(-1)^{c_i}\sqrt{1-x_i^2-y_i^2}).

Determine whether there exists a net of a net of the convex hull of given points, which is a path. If exists, compute the largest length of such path.

Constraints

• 4 \leq N \leq 14
• -1\leq x_i,y_i\leq 1
• c_i is 0 or 1
• x_i^2+y_i^2\leq 1
• No two given points coincide.
• For all four different given points p,q,r,s, the distance between s and the plain on which p,q,r exist is at least 10^{-5}.

Sample Input 1

4
0.000000 0.000000 1
0.000000 0.000000 0
1.000000 0.000000 1
0.000000 1.000000 0

Sample Output 1

13.899494936612

The following net of net is optimal.

Figure: the optimal net of the net.

Sample Input 2

6
-0.322191 -0.852465 0
-0.463288 -0.553583 1
0.378710 -0.346882 1
-0.489727 0.488028 0
-0.731142 0.227066 1
0.254757 -0.899035 0

Sample Output 2

22.950966056549

Sample Input 3

8
0.837078 0.492956 1
0.360579 -0.565500 0
-0.367448 -0.492394 1
0.491637 -0.658814 1
-0.505114 -0.538563 1
0.544637 0.592884 1
-0.622207 -0.379934 1
0.402129 0.684158 1

Sample Output 3

28.879053537910

Sample Input 4

4
0.800000 0.600000 0
1.000000 0.000000 1
-0.280000 -0.960000 1
0.000000 0.000000 0

Sample Output 4

13.284042973728

Story

You heard a song consisting of N notes in fits and starts. You want to guess whether a phrase consisting of M sounds was included in this song. You also want to consider cases where the phrase is included in a different key than the original.

Problem Statement

You are given two sequences of non-negative integers, A = (A_1, \dots, A_N) and B = (B_1, \dots, B_M), each of length N and M, respectively.

Find the number of integers i that satisfy 1 \le i \le N - M + 1 and meet the following condition:

Condition

Define a contiguous subsequence C of length M of A as C = (A_i, \dots, A_{i + M - 1}). Next, update all elements of the sequences B and C that are 0 with any positive real number (the updated values may be different for each element). Then, determine an arbitrary positive real number t, and multiply all elements of sequence C by t. By doing so, the sequences B and C can be made identical.

Constraints

• 1 \leq M \leq N \leq 5 \times 10^5
• 0 \leq A_i \leq 5 \times 10^5 (i = 1, \ldots, N)
• 0 \leq B_i \leq 5 \times 10^5 (i = 1, \ldots, M)

Sample Input 1

9 4
9 3 0 0 2 99 4 0 0
6 2 0 4

Sample Output 1

4

For i = 1, update B to (6, 2, 5, 4) and C = (9, 3, 0, 0) to (9, 3, 7.5, 6), and take t = 2/3. Finally, B and C will match.

For i = 2, 3, 4, it is possible to make B and C match by performing appropriate operations, but for i = 5, 6, it is impossible.

Therefore, since i = 1, 2, 3, 4 meet the condition, output 4 as the answer.

Sample Input 2

8 2
0 0 0 0 0 0 0 0
0 0

Sample Output 2

7

Problem Statement

You are given N distinct integer grid points (X_i, Y_i) \ (i = 1, 2, \dots, N) in the plane, each of which has an integer score P_i. You can choose an arbitrary number of grid points among them under the following condition. Find the maximum value of the sum of the scores of chosen grid points.

Condition: A grid point dominated by a convex combination of the chosen grid points must be chosen. That is, for each k = 1, 2, \dots, N, if there exists a tuple (\lambda_1, \lambda_2, \dots, \lambda_N) of N nonnegative reals with the following conditions, then (X_k, Y_k) is chosen:

• \lambda_i > 0 \implies (X_i, Y_i) is chosen.
• \sum_{i=1}^N \lambda_i = 1.
• \sum_{i=1}^N \lambda_i X_i \geq X_k.
• \sum_{i=1}^N \lambda_i Y_i \geq Y_k.

Constraints

• 1 \leq N \leq 200
• 1 \leq X_i \leq 10^9 \ \ (1 \leq i \leq N)
• 1 \leq Y_i \leq 10^9 \ \ (1 \leq i \leq N)
• (X_i, Y_i) \neq (X_j, Y_j) \ \ (i \neq j)
• |P_i| \leq 10^7 \ \ (1 \leq i \leq N)

Sample Input 1

3
1 4 2
4 1 3
2 2 -4

Sample Output 1

3

It is optimal to choose only (X_2, Y_2) = (4, 1). If you choose (X_1, Y_1) = (1, 4) in addition, then for example \lambda_1 = 0.4 and \lambda_2 = 0.6 satisfy

\[ \lambda_1 + \lambda_2 = 0.4 + 0.6 = 1\\[1mm] \lambda_1 X_1 + \lambda_2 X_2 = 0.4 \times 1 + 0.6 \times 4 = 2.8 \geq 2 = X_3\\[1mm] \lambda_1 Y_1 + \lambda_2 Y_2 = 0.4 \times 4 + 0.6 \times 1 = 2.2 \geq 2 = Y_3, \]

and hence (X_3, Y_3) = (2, 2) must be chosen in addition, which decreases the sum of scores as a result.

Sample Input 2

3
1 4 2
4 1 3
2 2 -1

Sample Output 2

4

It is optimal to choose all the grid points.

Sample Input 3

3
1 4 2
4 1 3
1 1 -6

Sample Output 3

0

It is sometimes optimal to choose no grid point.

Problem Statement

You are given positive integers X, M \ (X \leq M).

You like positive integers less than or equal to M, but you hate X as the exception. So you decide to construct a set S satisfying the following conditions.

• S consists of distinct positive integers less than or equal to 10^5.
• S has at most 20 elements.
• For all positive intergers k satisfying 1 \leq k \leq M and k \neq X, there exists at least one subset of S such that the sum of its elements equals to k.
• There is no subset of S such that the sum of its elements equals to X.

Determine whether such a set S exists, and if so, construct one example.

Solve T test cases for each input file.

Constraints

• 1 \leq T \leq 100
• 1 \leq X \le M \leq 10^5
• M \geq 2
• All input values are integers.

Sample Input 1

3
4 6
3 7
11 11

Sample Output 1

3
1 2 5
-1
4
1 2 3 4

• In the first case, S=\lbrace 1, 2, 5 \rbrace is one example of S．
• In the second case, there is no S satisfying the conditions.
• In the third case, S=\lbrace 1, 2, 3, 4 \rbrace is one example of S．

Problem Statement

DEGwer owns a rectangular land [-W, W] \times [-H, H] in the plane, and he is engaged in farming there. He is suffering from damage caused by birds and beasts, and he has decided to stretch beams that burn out creatures invading his land. Specifically, he will construct pillars having a sign, either + or -, on integer grid points in his land, and then stretch a beam as a segment between two pillars having different signs. However, if two beams share a point without a pillar, then something horrible happens because of resonance of beam energy, and hence he has to let any two beams not share a point without a pillar.

DEGwer has decided N integer grid points (X_i, Y_i) \ (i = 1, 2, \dots, N) on which he will construct the pillars. These grid points include the four corners of his land, and any three among these grid points are not on a single line. Your mission is to maximize the number of stretched beams by determining the sign of each pillar and between which pillars beams are stretched.

Constraints

• 1 \le W \le 10^9
• 1 \le H \le 10^9
• 4 \le N \le 10^5
• -W \le X_i \le W \ \ (1 \leq i \leq N)
• -H \le Y_i \le H \ \ (1 \leq i \leq N)
• (X_i, Y_i) \neq (X_j, Y_j) \ \ (i \neq j)
• There exists an index i such that (X_i, Y_i) = (\pm W, \pm H) (for any pair of signs).
• When i \neq j \neq k \neq i, the three grid points (X_i, Y_i), (X_j, Y_j), and (X_k, Y_k) are not on a single line.

Sample Input 1

1 1
4
1 1
-1 1
-1 -1
1 -1

Sample Output 1

+-+-
4
1 2
2 3
3 4
4 1

DEGwer's land is [-1, 1] \times [-1, 1], and he will construct four pillars on the four corners. If you assign alternating signs to the corner pillars in (counter)clockwise direction, you can stretch a beam between any adjacent pillars, and this is maximum.

Sample Input 2

1 2
5
1 2
-1 2
0 1
-1 -2
1 -2

Sample Output 2

+-++-
6
1 2
2 4
4 5
5 1
2 3
3 5

DEGwer's land is [-1, 1] \times [-2, 2], and he will construct five pillars on the grid point (0, 1) in addition to the four corners. If you assign alternating signs to the corner pillars in (counter)clockwise direction and an arbitrary sign to the pillar on (0, 1), you can stretch six beams in total as Sample Output 2. It can be proved that seven beams cannot be stretched, so this is an example of a solution.