Problem Statement

You are given a positive integer N.

You will print a document consisting of N pages on sheets of copy paper.

You will use double-sided printing, so one page can be printed on each of the front and back of a sheet.

Find the minimum number of sheets of copy paper needed to print all N pages.

Constraints

• 1\le N\le 100
• N is an integer.

Sample Input 1

3

Sample Output 1

2

By printing on both sides of one sheet of copy paper and on one side of another, you can print 3 pages using 2 sheets.

Sample Input 2

6

Sample Output 2

3

Sample Input 3

59

Sample Output 3

30

Problem Statement

There are N cards numbered 1 to N, each with a distinguishable front and back. Initially, they are stacked in the order 1,2,\ldots,N from the top, all face up.

Takahashi performs Q operations on this stack. The i-th operation (1\leq i\leq Q) is as follows.

Flip the top K_i cards over together as a single block and put them back in place.
This reverses the top-to-bottom order of the top K_i cards and also turns each of those cards over.

Find the order and orientation of the cards after all operations.
Specifically, for each i=1,2,\ldots,N, let X_i be the number written on the i-th card from the top; print X_i if that card is face up, and -X_i if it is face down.

Constraints

• 1 \leq N,Q \leq 100
• 1 \leq K_i \leq N
• All input values are integers.

Sample Input 1

5 2
3 5

Sample Output 1

-5
-4
1
2
3

Below, we write "i up" for the card numbered i placed face up, and "i down" for the card numbered i placed face down.

Initially, the states of the stacked cards, from the top, are (1 up, 2 up, 3 up, 4 up, 5 up).
The 1-st operation flips the top 3 cards together, so the states become (3 down, 2 down, 1 down, 4 up, 5 up) from the top.
Next, the 2-nd operation flips all of the top 5 cards together, so the states become (5 down, 4 down, 1 up, 2 up, 3 up) from the top.

Thus, print -5,-4,1,2,3 in this order, one per line.

Sample Input 2

1 1
1

Sample Output 2

-1

After the single operation, the card numbered 1 is face down. Thus, print -1.

Problem Statement

AtCoder Village is holding an election to choose its mayor.
There are N candidates, numbered candidate 1, candidate 2, \ldots, candidate N.

There are M voters. The i-th voter (1\leq i\leq M) has candidate A_i as their first choice and candidate B_i as their second choice.

When exactly one of the candidates withdraws, each voter votes as follows.

• If the voter's first-choice candidate has not withdrawn, the voter votes for their first-choice candidate.
• If the voter's first-choice candidate has withdrawn, the voter votes for their second-choice candidate.

Among the candidates who have not withdrawn, the candidate with the most votes wins. If there are multiple such candidates, the one with the smallest number wins.

For each k=1,2,\ldots,N, find the number of the candidate who wins when only candidate k withdraws.

Constraints

• 2 \leq N \leq 2\times 10^5
• 1 \leq M \leq 2\times 10^5
• 1 \leq A_i,B_i \leq N
• A_i\neq B_i
• All input values are integers.

Sample Input 1

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

Sample Output 1

3
1
1
2
1

When only candidate 1 withdraws, the voters vote as follows.

• Voter 1's first-choice candidate has withdrawn, so they vote for their second-choice candidate, candidate 3.
• Voter 2's first-choice candidate has withdrawn, so they vote for their second-choice candidate, candidate 3.
• Voter 3's first-choice candidate has not withdrawn, so they vote for their first-choice candidate, candidate 2.
• Voter 4's first-choice candidate has not withdrawn, so they vote for their first-choice candidate, candidate 2.
• Voter 5's first-choice candidate has not withdrawn, so they vote for their first-choice candidate, candidate 3.
• Voter 6's first-choice candidate has not withdrawn, so they vote for their first-choice candidate, candidate 4.

Thus, candidate 2 receives 2 votes, candidate 3 receives 3 votes, and candidate 4 receives 1 vote, so candidate 3, who has the most votes, wins.

When each of the other candidates withdraws instead, the results are as follows.

• When only candidate 2 withdraws, candidate 1 receives 4 votes, candidate 3 receives 1 vote, and candidate 4 receives 1 vote, so candidate 1, who has the most votes, wins.
• When only candidate 3 withdraws, candidate 1 receives 2 votes, candidate 2 receives 2 votes, and candidate 4 receives 2 votes, so candidate 1, who has the smallest number among those with the most votes, wins.
• When only candidate 4 withdraws, candidate 1 receives 2 votes, candidate 2 receives 3 votes, and candidate 3 receives 1 vote, so candidate 2, who has the most votes, wins.
• When only candidate 5 withdraws, candidate 1 receives 2 votes, candidate 2 receives 2 votes, candidate 3 receives 1 vote, and candidate 4 receives 1 vote, so candidate 1, who has the smallest number among those with the most votes, wins.

Thus, print 3,1,1,2,1 in this order, one per line.

Problem Statement

There is a robot on a number line. Initially, the robot is at coordinate 0. Also, Takahashi has an integer sequence A=(A_1,A_2,\ldots,A_N) of length N.

Takahashi performs the following steps in order.

1. Choose at most 1 element of A and flip its sign. That is, choose 0 or 1 index i satisfying 1\leq i\leq N, and replace A_i with -A_i.

2. Start the robot. After starting, the robot makes N moves. In the i-th move (1\leq i\leq N), letting x be its current coordinate, the robot moves in a straight line to coordinate x+A_i.

Takahashi wants to maximize the number of integer coordinates that the robot passes through at least once.
Find the maximum possible value of "the number of integer coordinates that the robot passes through at least once" when Takahashi acts optimally.

Here, the robot moves continuously. When a move takes the robot from coordinate S to coordinate T, it is considered to have passed through every integer coordinate between S and T, inclusive.

Constraints

• 1 \leq N \leq 2\times 10^5
• -10^9 \leq A_i \leq 10^9
• A_i\neq 0
• All input values are integers.

Sample Input 1

3
-2 3 -2

Sample Output 1

8

Initially, A=(-2,3,-2). If Takahashi flips the sign of A_2, then A=(-2,-3,-2). In this case, the robot moves as follows.

• In its 1-st move, the robot moves from 0 to -2. The integer coordinates it passes through in this move are -2,-1,0.
• In its 2-nd move, the robot moves from -2 to -5. The integer coordinates it passes through in this move are -5,-4,-3,-2.
• In its 3-rd move, the robot moves from -5 to -7. The integer coordinates it passes through in this move are -7,-6,-5.

Thus, the integer coordinates the robot passes through at least once are the 8 coordinates -7,-6,-5,-4,-3,-2,-1,0, and this is the maximum possible count, so print 8.

Note that if Takahashi did not flip the sign of any element, the robot would move as 0\to -2\to 1\to -1, and the integer coordinates it passes through at least once would be the 4 coordinates -2,-1,0,1.

Sample Input 2

2
2 3

Sample Output 2

6

If no element of A is changed, the robot moves as 0\to 2\to 5, and the integer coordinates it passes through at least once are the 6 coordinates 0,1,2,3,4,5.
This is the maximum possible count, so print 6.

Problem Statement

There are N strings of length M consisting of lowercase English letters. The i-th string (1\leq i\leq N) is S_i.

Find the number of integer pairs (i,j) (1\leq i < j \leq N) satisfying the following condition.

• The Hamming distance between S_i and S_j is at most 2.

Constraints

• 2 \leq N \leq 2\times 10^5
• 2 \leq M \leq 6
• N and M are integers.
• S_i is a string of length M consisting of lowercase English letters.

Sample Input 1

3 3
abc
abd
bac

Sample Output 1

2

• The Hamming distance between S_1=abc and S_2=abd is 1.
• The Hamming distance between S_1=abc and S_3=bac is 2.
• The Hamming distance between S_2=abd and S_3=bac is 3.

Thus, the pairs satisfying the condition are the 2 pairs (i,j)=(1,2), (1,3), so print 2.

Sample Input 2

9 5
aaaaa
aaaaa
aaaab
aaaba
aaabb
aabaa
aabab
aabba
aabbb

Sample Output 2

31

The same string may appear multiple times.

Problem Statement

You are given integers N,Q and integer sequences A=(A_1,A_2,\ldots,A_N), B=(B_1,B_2,\ldots,B_N) of length N.

You are given Q queries, so answer each of them. In each query, you are given an integer x; find the value of \displaystyle \sum_{i=1}^N ((x+A_i) \bmod B_i).

Constraints

• 1\le N\le 5\times 10^5
• 0\le A_i < B_i \le 5\times 10^5
• 1\le Q\le 2\times 10^5
• 0\le x\le 5\times 10^5
• All input values are integers.

Sample Input 1

3
1 3
2 5
0 1
5
0
1
2
3
200000

Sample Output 1

3
5
4
1
2

The answer to each query is obtained as follows.

• In the 1-st query, x=0, so the answer is ((0+1)\bmod 3)+((0+2)\bmod 5)+((0+0)\bmod 1)=1+2+0=3.
• In the 2-nd query, x=1, so the answer is ((1+1)\bmod 3)+((1+2)\bmod 5)+((1+0)\bmod 1)=2+3+0=5.
• In the 3-rd query, x=2, so the answer is ((2+1)\bmod 3)+((2+2)\bmod 5)+((2+0)\bmod 1)=0+4+0=4.
• In the 4-th query, x=3, so the answer is ((3+1)\bmod 3)+((3+2)\bmod 5)+((3+0)\bmod 1)=1+0+0=1.
• In the 5-th query, x=200000, so the answer is ((200000+1)\bmod 3)+((200000+2)\bmod 5)+((200000+0)\bmod 1)=0+2+0=2.

Sample Input 2

3
2 3
5 7
0 9
4
9
3
6
17

Sample Output 2

2
6
12
10

Sample Input 3

8
0 10
3 8
1 3
5 7
4 8
4 9
2 6
5 7
7
130140
70510
22719
104735
119072
127841
191631

Sample Output 3

16
21
31
29
19
21
27

Problem Statement

You are given integers N,K. It is guaranteed that the given integers satisfy \displaystyle K \le \frac N2.

For permutations P=(P_1,P_2,\ldots,P_N),Q=(Q_1,Q_2,\ldots,Q_N) of (1,2,\ldots,N), define f(P,Q) as follows:

N people, person 1 through person N, participated in 2 contests, contest A and contest B. Person i (1\le i\le N) placed P_i-th in contest A and Q_i-th in contest B.

Consider choosing 2K of these N people by the following 2 selection methods.

• Method ①: Choose the K people with the best ranks in contest A. Then, among the N-K people not yet chosen, choose the K people with the best ranks in contest B.
• Method ②: Choose the K people with the best ranks in contest B. Then, among the N-K people not yet chosen, choose the K people with the best ranks in contest A.

Let f(P,Q) be the number of people who are chosen by method ① but not chosen by method ②.

There are N!^2 pairs (P,Q) of permutations of (1,2,\ldots,N). Find the sum of f(P,Q) over all of them, modulo 998244353.

You are given T test cases; solve each of them.

Constraints

• 1\le T\le 2\times 10^5
• 2\le N\le 10^6
• \displaystyle 1\le K \le \frac N2
• The sum of N over all test cases is at most 10^6.
• All input values are integers.

Sample Input 1

4
3 1
6 3
9 2
483 101

Sample Output 1

6
0
982675409
845255482

Consider the 1-st test case.

For example, when P=(2,1,3),Q=(3,1,2), the people chosen by method ① are persons 2 and 3, and the people chosen by method ② are persons 1 and 2. Therefore, f(P,Q)=1 for this pair P,Q.

There are 6 pairs (P,Q) with f(P,Q)=1, and f(P,Q)=0 holds for the remaining 30 pairs (P,Q). Therefore, the answer is 6\times 1+30\times 0=6.