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

You are given an integer N and a sequence S=(S_1,\ldots,S_N) of length N.

Find a sequence A=(A_1,\ldots,A_N) of length N that satisfies the following condition for all k=1,\ldots,N:

• A_1+A_2+\ldots+A_k = S_k.

Such a sequence A always exists and is unique.

Constraints

• 1 \leq N \leq 10
• -10^9\leq S_i \leq 10^9
• All values in the input are integers.

Sample Input 1

3
3 4 8

Sample Output 1

3 1 4

The sequence in the output actually satisfies all the conditions:

• A_1=3=S_1;
• A_1+A_2=3+1=4=S_2;
• A_1+A_2+A_3=3+1+4=8=S_3.

Sample Input 2

10
314159265 358979323 846264338 -327950288 419716939 -937510582 97494459 230781640 628620899 -862803482

Sample Output 2

314159265 44820058 487285015 -1174214626 747667227 -1357227521 1035005041 133287181 397839259 -1491424381

Problem Statement

You are given strings S and T. S consists of lowercase English letters, and T is obtained by inserting a lowercase English letter into S.

Find the position of the inserted character in T.
If there are multiple candidates, find any of them.

Constraints

• 1 \leq |S| \leq 5\times 10^5
• S consists of lowercase English letters.
• T is obtained by inserting a lowercase English letter into S.

Sample Input 1

atcoder
atcorder

Sample Output 1

5

The 5-th character from the beginning of T, r, is inserted.

Sample Input 2

million
milllion

Sample Output 2

5

One of the 3-rd, 4-th, and 5-th characters from the beginning of T is inserted. Thus, printing any one of 3, 4, and 5 is accepted.

Sample Input 3

vvwvw
vvvwvw

Sample Output 3

3

Problem Statement

You are given an integer K greater than or equal to 2.
Find the minimum positive integer N such that N! is a multiple of K.

Here, N! denotes the factorial of N. Under the Constraints of this problem, we can prove that such an N always exists.

Constraints

• 2\leq K\leq 10^{12}
• K is an integer.

Sample Input 1

30

Sample Output 1

5

• 1!=1
• 2!=2\times 1=2
• 3!=3\times 2\times 1=6
• 4!=4\times 3\times 2\times 1=24
• 5!=5\times 4\times 3\times 2\times 1=120

Therefore, 5 is the minimum positive integer N such that N! is a multiple of 30. Thus, 5 should be printed.

Sample Input 2

123456789011

Sample Output 2

123456789011

Sample Input 3

280

Sample Output 3

7

Problem Statement

There is a monster with initial stamina N.
Takahashi repeatedly attacks the monster while the monster's stamina remains 1 or greater.

An attack by Takahashi reduces the monster's stamina by 2 with probability \frac{P}{100} and by 1 with probability 1-\frac{P}{100}.

Find the expected value, modulo 998244353 (see Notes), of the number of attacks before the monster's stamina becomes 0 or less.

Notes

We can prove that the sought expected value is always a finite rational number. Moreover, under the Constraints of this problem, when the value is represented as \frac{P}{Q} by two coprime integers P and Q, we can show that there exists a unique integer R such that R \times Q \equiv P\pmod{998244353} and 0 \leq R \lt 998244353. Print such R.

Constraints

• 1 \leq N \leq 2\times 10^5
• 0 \leq P \leq 100
• All values in the input are integers.

Sample Input 1

3 10

Sample Output 1

229596204

An attack by Takahashi reduces the monster's stamina by 2 with probability \frac{10}{100}=\frac{1}{10} and by 1 with probability \frac{100-10}{100}=\frac{9}{10}.

• The monster's initial stamina is 3.
• After the first attack, the monster's stamina is 2 with probability \frac{9}{10} and 1 with probability \frac{1}{10}.
• After the second attack, the monster's stamina is 1 with probability \frac{81}{100}, 0 with probability \frac{18}{100}, and -1 with probability \frac{1}{100}. With probability \frac{18}{100}+\frac{1}{100}=\frac{19}{100}, the stamina becomes 0 or less, and Takahashi stops attacking after two attacks.
• If the stamina remains 1 after two attacks, the monster's stamina always becomes 0 or less by the third attack, so he stops attacking after three attacks.

Therefore, the expected value is 2\times \frac{19}{100}+3\times\left(1-\frac{19}{100}\right)=\frac{281}{100}. Since 229596204 \times 100 \equiv 281\pmod{998244353}, print 229596204.

Sample Input 2

5 100

Sample Output 2

3

Takahashi's attack always reduces the monster's stamina by 2. After the second attack, the stamina remains 5-2\times 2=1, so the third one is required.

Sample Input 3

280 59

Sample Output 3

567484387

Problem Statement

There are N towns numbered 1,\ldots,N and M roads numbered 1,\ldots,M.

Road i connects towns A_i and B_i. When you use a road, your score changes as follows:

• when you move from town A_i to town B_i using road i, your score increases by C_i; when you move from town B_i to town A_i using road i, your score decreases by C_i.

Your score may become negative.

Answer the following Q questions.

• If you start traveling from town X_i with initial score 0, find the maximum possible score when you are at town Y_i.
  Here, if you cannot get from town X_i to town Y_i, print nan instead; if you can have as large a score as you want when you are at town Y_i, print inf instead.

Constraints

• 2\leq N \leq 10^5
• 0\leq M \leq 10^5
• 1\leq Q \leq 10^5
• 1\leq A_i,B_i,X_i,Y_i \leq N
• 0\leq C_i \leq 10^9
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

-2
inf
nan

For the first question, if you use road 5 to move from town 5 to town 3, you can have a score -2 when you are at town 3.
Since you cannot make the score larger, the answer is -2.

For the second question, you can have as large a score as you want when you are at town 2 if you travel as follows: repeatedly "use road 2 to move from town 1 to town 2 and then use road 1 to move from town 2 to town 1" as many times as you want, and finally use road 2 to move from town 1 to town 2.

For the third question, you cannot get from town 3 to town 1.

Sample Input 2

2 1 1
1 1 1
1 1

Sample Output 2

inf

The endpoints of a road may be the same, and so may the endpoints given in a question.

Sample Input 3

9 7 5
3 1 4
1 5 9
2 6 5
3 5 8
9 7 9
3 2 3
8 4 6
2 6
4 3
3 8
3 2
7 9

Sample Output 3

inf
nan
nan
inf
-9

Problem Statement

We have an infinite hexagonal grid shown below.

A hexagonal cell is represented as (i,j) with two integers i and j.
Cell (i,j) is adjacent to the following six cells:

• (i-1,j-1)
• (i-1,j)
• (i,j-1)
• (i,j+1)
• (i+1,j)
• (i+1,j+1)

Let us define the distance between two cells X and Y by the minimum number of moves required to travel from cell X to cell Y by repeatedly moving to an adjacent cell.
For example, the distance between cells (0,0) and (1,1) is 1, and the distance between cells (2,1) and (-1,-1) is 3.

You are given N cells (X_1,Y_1),\ldots,(X_N,Y_N).
How many ways are there to choose one or more from these N cells so that the distance between any two of the chosen cells is at most D?
Find the count modulo 998244353.

Constraints

• 1 \leq N \leq 300
• -10^9\leq X_i,Y_i \leq 10^9
• 1\leq D \leq 10^{10}
• (X_i,Y_i) are pairwise distinct.
• All values in the input are integers.

Sample Input 1

3 1
0 0
0 1
1 0

Sample Output 1

5

There are five possible sets of the chosen cells: \{(0,0)\},\{(0,1)\},\{(1,0)\},\{(0,0),(0,1)\}, and \{(0,0),(1,0)\}.

Sample Input 2

9 1
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2

Sample Output 2

33

Sample Input 3

5 10000000000
314159265 358979323
846264338 -327950288
-419716939 937510582
-97494459 -230781640
628620899 862803482

Sample Output 3

31

Problem Statement

You are given N strings S_1,S_2,\ldots, S_N. Let M = \displaystyle\sum_{i=1}^N \frac{|S_i|(|S_i|+1)}{2}.
For a string S and integers L and R, let us denote by S[L, R] the substring consisting of the L-th through R-th characters of S.

A sequence of triples of integers ((K_1, L_1, R_1), (K_2, L_2, R_2), \ldots, (K_M, L_M, R_M)) of length M satisfies the following conditions:

• The M elements are pairwise distinct.
• For all 1 \leq i \leq M, it holds that 1 \leq K_i \leq N and 1 \leq L_i \leq R_i \leq |S_{K_i}|.
• For all 1 \leq i \leq j \leq M, it holds that S_{K_i}[L_i, R_i] \leq S_{K_j}[L_j, R_j] in the lexicographical order.

You are given Q integers x_1,x_2,\ldots, x_Q between 1 and M, inclusive. For each 1 \leq i \leq Q, find a possible instance of (K_{x_i}, L_{x_i}, R_{x_i}). We can prove that there always exists a sequence of triples that satisfies the conditions. If multiple triples satisfy the conditions, print any of them. In addition, among different x_i's, the conforming sequence of triples does not have to be common.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq \lvert S_i\rvert \leq 10^5
• \displaystyle\sum_{i=1}^N \lvert S_i\rvert\leq 10^5
• 1 \leq Q \leq 2\times 10^5
• 1 \leq x_1<x_2<\cdots<x_Q \leq \displaystyle\sum_{i=1}^N \frac{|S_i|(|S_i|+1)}{2}
• N,Q,x_1,x_2,\ldots,x_Q are integers.
• S_i is a string consisting of lowercase English letters.

Sample Input 1

2
abab
cab
2
5 14

Sample Output 1

1 3 4
2 1 1

We have M=16. One possible sequence of triples that satisfies the conditions is ((1,1,1), (1,3,3), (2,2,2), (1,1,2), (1,3,4), (2,2,3), (1,1,3), (1,1,4), (1,2,2), (1,4,4), (2,3,3), (1,2,3), (1,2,4), (2,1,1), (2,1,2), (2,1,3)). The corresponding sequence of S_{K_i}[L_i, R_i] for these (K_i,L_i, R_i) in this order is (a, a, a, ab, ab, ab, aba, abab, b, b, b, ba, bab, c, ca, cab).

Note that the sequence satisfies the conditions even if we swap the 5-th element (1,3,4) with the 4-th or 6-th one, so (K_{x_1}, L_{x_1}, R_{x_1})=(1,1,2), (2,2,3) will also be accepted.

Sample Input 2

3
a
a
ba
2
1 2

Sample Output 2

1 1 1
1 1 1

We have M=5. The sequence of triples that satisfies the conditions can be
(1,1,1), (2,1,1), (3,2,2), (3,1,1), (3,1,2) or (2,1,1), (3,2,2), (1,1,1), (3,1,1), (3,1,2), for example.

Note that, for (K_{x_i}, L_{x_i}, R_{x_i}) that you print, the conforming sequence whose x_i-th element is (K_{x_i}, L_{x_i}, R_{x_i}) does not have to be common among different i; in other words, there does not necessarily have to exist a sequence whose "x_i-th element is (K_{x_i}, L_{x_i}, R_{x_i}) for all 1\leq i\leq Q."

Sample Input 3

10
gxgpuamkx
szhkbpphykin
ezplvfja
mopodotkrj
rimlvumuar
nexcfyce
eurgvjyos
dhvuyfvt
nrdyluacvra
ggwnpnzij
6
74 268 310 380 455 489

Sample Output 3

3 1 2
4 4 5
4 3 7
9 6 6
6 6 6
2 2 12