Problem Statement

You are given a positive integer A and a positive odd integer B.

Output the integer whose difference from the real number \dfrac AB is the smallest.

It can be proved that, under the constraints, such an integer is unique.

Constraints

• 1 \le A \le 407
• 1 \le B \le 407
• B is odd.
• All input values are integers.

Sample Input 1

4 7

Sample Output 1

1

We have \dfrac AB = \dfrac47 = 0.5714\ldots. The difference between \dfrac AB and 1 is \dfrac37 = 0.4285\ldots, and no integer has a smaller difference.

Thus, print 1.

Sample Input 2

407 29

Sample Output 2

14

We have \dfrac AB = \dfrac{407}{29} = 14.0344\ldots. The difference between \dfrac AB and 14 is \dfrac1{29} = 0.0344\ldots, and no integer has a smaller difference.

Thus, print 14.

Sample Input 3

22 11

Sample Output 3

2

\dfrac AB may itself be an integer.

Problem Statement

There is a grid with H rows from top to bottom and W columns from left to right. Each square has a piece placed on it or is empty.

The state of the grid is represented by H strings S_1, S_2, \ldots, S_H, each of length W.
If the j-th character of S_i is #, the square at the i-th row from the top and j-th column from the left has a piece on it;
if the j-th character of S_i is ., the square at the i-th row from the top and j-th column from the left is empty.

How many squares in the grid have pieces on them?

Constraints

• 1\leq H,W \leq 10
• H and W are integers.
• S_i is a string of length W consisting of # and ..

Sample Input 1

3 5
#....
.....
.##..

Sample Output 1

3

The following three squares have pieces on them:

• the square at the 1-st row from the top and 1-st column from the left;
• the square at the 3-rd row from the top and 2-nd column from the left;
• the square at the 3-rd row from the top and 3-rd column from the left.

Thus, 3 should be printed.

Sample Input 2

1 10
..........

Sample Output 2

0

Since no square has a piece on it, 0 should be printed.

Sample Input 3

6 5
#.#.#
....#
..##.
####.
..#..
#####

Sample Output 3

16

Problem Statement

There are N boxes numbered 1,2,\dots,N. Initially, all boxes are empty.

Q balls will come in order.
Takahashi will put the balls into the boxes according to the sequence X=(X_1,X_2,\dots,X_Q).
Specifically, he performs the following process for the i-th ball:

• If X_i \ge 1: Put this ball into box X_i.
• If X_i = 0: Put this ball into the box with the smallest number among those containing the fewest balls.

Find which box each ball was put into.

Constraints

• All input values are integers.
• 1 \le N \le 100
• 1 \le Q \le 100
• 0 \le X_i \le N

Sample Input 1

4 5
2 0 3 0 0

Sample Output 1

2 1 3 4 1

There are 4 boxes, and 5 balls come.

• Initially, all boxes are empty.
  • The numbers of balls in box 1,2,3,4 are 0,0,0,0, respectively.
• Since X_1=2, put the 1st ball into box 2.
  • The numbers of balls in box 1,2,3,4 are 0,1,0,0, respectively.
• Since X_2=0, put the 2nd ball into box 1, which has the smallest number among those containing the fewest balls.
  • The numbers of balls in box 1,2,3,4 are 1,1,0,0, respectively.
• Since X_3=3, put the 3rd ball into box 3.
  • The numbers of balls in box 1,2,3,4 are 1,1,1,0, respectively.
• Since X_4=0, put the 4th ball into box 4, which has the smallest number among those containing the fewest balls.
  • The numbers of balls in box 1,2,3,4 are 1,1,1,1, respectively.
• Since X_5=0, put the 5th ball into box 1, which has the smallest number among those containing the fewest balls.
  • The numbers of balls in box 1,2,3,4 are 2,1,1,1, respectively.

The balls were put into boxes 2,1,3,4,1 in order. Thus, output 2 1 3 4 1.

Sample Input 2

3 7
1 1 0 0 0 0 0

Sample Output 2

1 1 2 3 2 3 1

Sample Input 3

6 20
4 6 0 3 4 2 6 5 2 3 0 3 2 5 0 3 5 0 2 0

Sample Output 3

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

Problem Statement

There are N customers numbered 1 to N, and M canned juices numbered 1 to M.

Customer i (1 \leq i \leq N) has a wish list of length L_i. The j-th item (1 \leq j \leq L_i) from the top of customer i's wish list is canned juice X_{i,j}. For any customer i, the numbers X_{i, 1}, \dots, X_{i, L_i} on customer i's wish list are distinct.

Customers 1, \dots, N, in this order, will now choose their beverages, following the procedure below.

• If the customer's wish list contains a canned juice that has not yet been chosen by anyone at that point, they choose the canned juice whose number appears earliest in their wish list. Otherwise, they choose water.

Determine which beverage each customer gets.

Constraints

• 1 \leq N \leq 100
• 1 \leq M \leq 100
• 1 \leq L_i \leq M (1 \leq i \leq N)
• 1 \leq X_{i,j} \leq M (1 \leq i \leq N, 1 \leq j \leq L_i)
• X_{i, 1}, \dots, X_{i, L_i} are distinct. (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

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

Sample Output 1

3
2
0
5

Among the numbers on customer 1's wish list, the canned juices not yet chosen by anyone are 3, 1, 2. The one appearing earliest in the list is 3, so customer 1 chooses canned juice 3.

Among the numbers on customer 2's wish list, the canned juices not yet chosen by anyone are 2, 1. The one appearing earliest in the list is 2, so customer 2 chooses canned juice 2.

For the numbers on customer 3's wish list, all corresponding canned juices have already been chosen by someone at that point. Thus, customer 3 chooses water.

Among the numbers on customer 4's wish list, the canned juices not yet chosen by anyone are 5, 1. The one appearing earliest in the list is 5, so customer 4 chooses canned juice 5.

Sample Input 2

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

Sample Output 2

3
5
1
4
2
0

Problem Statement

Takahashi has N pairs of socks, and the i-th pair consists of two socks of color i. One day, after organizing his chest of drawers, Takahashi realized that he had lost one sock each of colors A_1, A_2, \dots, A_K, so he decided to use the remaining 2N-K socks to make \lfloor\frac{2N-K}{2}\rfloor new pairs of socks, each pair consisting of two socks. The weirdness of a pair of a sock of color i and a sock of color j is defined as |i-j|, and Takahashi wants to minimize the total weirdness.

Find the minimum possible total weirdness when making \lfloor\frac{2N-K}{2}\rfloor pairs from the remaining socks. Note that if 2N-K is odd, there will be one sock that is not included in any pair.

Constraints

• 1\leq K\leq N \leq 2\times 10^5
• 1\leq A_1 < A_2 < \dots < A_K \leq N
• All input values are integers.

Sample Input 1

4 2
1 3

Sample Output 1

2

Below, let (i,j) denote a pair of a sock of color i and a sock of color j.

There are 1, 2, 1, 2 socks of colors 1, 2, 3, 4, respectively. Creating the pairs (1,2),(2,3),(4,4) results in a total weirdness of |1-2|+|2-3|+|4-4|=2, which is the minimum.

Sample Input 2

5 1
2

Sample Output 2

0

The optimal solution is to make the pairs (1,1),(3,3),(4,4),(5,5) and leave one sock of color 2 as a surplus (not included in any pair).

Sample Input 3

8 5
1 2 4 7 8

Sample Output 3

2

Problem Statement

You are given two strings S and T. Determine whether it is possible to make S equal T by performing the following operation some number of times (possibly zero).

Between two consecutive equal characters in S, insert a character equal to these characters. That is, take the following three steps.

1. Let N be the current length of S, and S = S_1S_2\ldots S_N.
2. Choose an integer i between 1 and N-1 (inclusive) such that S_i = S_{i+1}. (If there is no such i, do nothing and terminate the operation now, skipping step 3.)
3. Insert a single copy of the character S_i(= S_{i+1}) between the i-th and (i+1)-th characters of S. Now, S is a string of length N+1: S_1S_2\ldots S_i S_i S_{i+1} \ldots S_N.

Constraints

• Each of S and T is a string of length between 2 and 2 \times 10^5 (inclusive) consisting of lowercase English letters.

Sample Input 1

abbaac
abbbbaaac

Sample Output 1

Yes

You can make S = abbaac equal T = abbbbaaac by the following three operations.

• First, insert b between the 2-nd and 3-rd characters of S. Now, S = abbbaac.
• Next, insert b again between the 2-nd and 3-rd characters of S. Now, S = abbbbaac.
• Lastly, insert a between the 6-th and 7-th characters of S. Now, S = abbbbaaac.

Thus, Yes should be printed.

Sample Input 2

xyzz
xyyzz

Sample Output 2

No

No sequence of operations makes S = xyzz equal T = xyyzz. Thus, No should be printed.

Problem Statement

Takahashi has N balls. Each ball has an integer not less than 2 written on it. He will insert them in a cylinder one by one. The integer written on the i-th ball is a_i.

The balls are made of special material. When k balls with k (k \geq 2) written on them line up in a row, all these k balls will disappear.

For each i (1 \leq i \leq N), find the number of balls after inserting the i-th ball.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 2 \leq a_i \leq 2 \times 10^5 \, (1 \leq i \leq N)
• All values in input are integers.

Sample Input 1

5
3 2 3 2 2

Sample Output 1

1
2
3
4
3

The content of the cylinder changes as follows.

• After inserting the 1-st ball, the cylinder contains the ball with 3.
• After inserting the 2-nd ball, the cylinder contains 3, 2 from bottom to top.
• After inserting the 3-rd ball, the cylinder contains 3, 2, 3 from bottom to top.
• After inserting the 4-th ball, the cylinder contains 3, 2, 3, 2 from bottom to top.
• After inserting the 5-th ball, the cylinder momentarily has 3, 2, 3, 2, 2 from bottom to top. The two consecutive balls with 2 disappear, and the cylinder eventually contains 3, 2, 3 from bottom to top.

Sample Input 2

10
2 3 2 3 3 3 2 3 3 2

Sample Output 2

1
2
3
4
5
3
2
3
1
0

Problem Statement

Solve the following problem for T test cases.

Given an integer N and a string S, find the number of strings X that satisfy all of the conditions below, modulo 998244353.

• X is a string of length N consisting of uppercase English letters.
• X is a palindrome.
• X \le S in lexicographical order.
  • That is, X=S or X is lexicographically smaller than S.

Constraints

• 1 \le T \le 250000
• N is an integer between 1 and 10^6 (inclusive).
• In a single input, the sum of N over the test cases is at most 10^6.
• S is a string of length N consisting of uppercase English letters.

Sample Input 1

5
3
AXA
6
ABCZAZ
30
QWERTYUIOPASDFGHJKLZXCVBNMQWER
28
JVIISNEOXHSNEAAENSHXOENSIIVJ
31
KVOHEEMSOZZASHENDIGOJRTJVMVSDWW

Sample Output 1

24
29
212370247
36523399
231364016

This input contains five test cases.

Test case #1:
The 24 strings satisfying the conditions are AAA, ABA, ACA,..., AXA.

Test case #2:
S may not be a palindrome.

Test case #3:
Be sure to find the count modulo 998244353.

Problem Statement

Given are sequences of N integers each: A = (A_1, \dots, A_N) and B = (B_1, \dots, B_N). Find the number of non-empty subsets S of \{1,2,\ldots,N\} that satisfy the following condition:

• \max_{i \in S} A_i \geq \sum_{i \in S} B_i.

Since the count can be enormous, print it modulo 998244353.

Constraints

• 1 \leq N \leq 5000
• 1 \leq A_i,B_i \leq 5000
• All values in input are integers.

Sample Input 1

2
3 1
1 2

Sample Output 1

2

\{1,2,\ldots,N\} has three subsets: \{1\}, \{2\}, and \{1,2\}.

• For S=\{1\}, we have \max_{i \in S} A_i=3 and \sum_{i \in S} B_i=1.
• For S=\{2\}, we have \max_{i \in S} A_i=1 and \sum_{i \in S} B_i=2.
• For S=\{1,2\}, we have \max_{i \in S} A_i=3 and \sum_{i \in S} B_i=3.

Thus, the condition \max_{i \in S} A_i \geq \sum_{i \in S} B_i is satisfied by two subsets: \{1\} and \{1,2\}.

Sample Input 2

2
1 1
2 2

Sample Output 2

0

There may be no subsets that satisfy the condition.

Sample Input 3

20
1937 3980 2689 1208 3640 1979 581 2271 4229 3948 3708 1522 4161 4661 3797 96 3388 3395 2920 2247
4485 2580 174 1156 3770 3396 3558 3500 3494 479 269 3383 1230 1711 3545 3919 134 475 3796 1017

Sample Output 3

476