Problem Statement

You are given N strings W_1,W_2,\dots,W_N consisting of lowercase English letters.
If one or more of these strings equal and, not, that, the, or you, then print Yes; otherwise, print No.

Constraints

• N is an integer between 1 and 100, inclusive.
• 1 \le |W_i| \le 50 (|W_i| is the length of W_i.)
• W_i consists of lowercase English letters.

Sample Input 1

10
in that case you should print yes and not no

Sample Output 1

Yes

We have, for instance, W_4= you, so you should print Yes.

Sample Input 2

10
in diesem fall sollten sie no und nicht yes ausgeben

Sample Output 2

No

None of the strings W_i equals any of and, not, that, the, and you.

Problem Statement

We have a board with R rows running horizontally and C columns running vertically. Let (i,j) denote the square at the i-th row from the top and j-th column from the left.

You are given characters B_{i,j} representing the current states of (i,j). . represents an empty square; # represents a square with a wall; 1, 2,\dots, 9 represent a square with a bomb of power 1,2,\dots,9, respectively.

At the next moment, all bombs will explode simultaneously. When a bomb explodes, every square whose Manhattan distance from the square with the bomb is not greater than the power of the bomb will turn into an empty square. Here, the Manhattan distance from (r_1,c_1) to (r_2,c_2) is |r_1-r_2|+|c_1-c_2|.

Print the board after the explosions.

Constraints

• 1\leq R,C \leq 20
• R and C are integers.
• Each B_{i,j} is one of ., #, 1, 2, \dots, 9.

Sample Input 1

4 4
.1.#
###.
.#2.
#.##

Sample Output 1

...#
#...
....
#...

• The explosion of the bomb at (1,2) will turn the blue squares and purple squares in the above figure into empty squares.
• The explosion of the bomb at (3,3) will turn the red squares and purple squares in the above figure into empty squares.

As seen in this sample, the explosion ranges of bombs may overlap.

Sample Input 2

2 5
..#.#
###.#

Sample Output 2

..#.#
###.#

There may be no bombs.

Sample Input 3

2 3
11#
###

Sample Output 3

...
..#

Sample Input 4

4 6
#.#3#.
###.#.
##.###
#1..#.

Sample Output 4

......
#.....
#....#
....#.

Problem Statement

You have N socks. The color of the i-th sock is A_i.

You want to perform the following operation as many times as possible. How many times can it be performed at most?

• Choose two same-colored socks that are not paired yet, and pair them.

Constraints

• 1\leq N \leq 5\times 10^5
• 1\leq A_i \leq 10^9
• All values in the input are integers.

Sample Input 1

6
4 1 7 4 1 4

Sample Output 1

2

You can do the operation twice as follows.

• Choose two socks with the color 1 and pair them.
• Choose two socks with the color 4 and pair them.

Then, you will be left with one sock with the color 4 and another with the color 7, so you can no longer do the operation. There is no way to do the operation three or more times, so you should print 2.

Sample Input 2

1
158260522

Sample Output 2

0

Sample Input 3

10
295 2 29 295 29 2 29 295 2 29

Sample Output 3

4

Problem Statement

The string 20230322 can be rearranged into 02320232, which is a repetition of 0232 twice.
Similarly, a string consisting of digits is said to be happy when it can be rearranged into (or already is) a repetition of some string twice.
You are given a string S consisting of digits. Find the number of pairs of integers (l,r) satisfying all of the following conditions.

• 1 \le l \le r \le |S|. (|S| is the length of S.)
• The (contiguous) substring formed of the l-th through r-th characters of S is happy.

Constraints

• S is a string consisting of digits whose length is between 1 and 5 \times 10^5, inclusive.

Sample Input 1

20230322

Sample Output 1

4

We have S= 20230322.

Here are the four pairs of integers (l,r) that satisfy the condition: (1,6), (1,8), (2,7), and (7,8).

Sample Input 2

0112223333444445555556666666777777778888888889999999999

Sample Output 2

185

S may begin with 0.

Sample Input 3

3141592653589793238462643383279502884197169399375105820974944

Sample Output 3

9

Problem Statement

We have a sequence of length N consisting of integers between 0 and M, inclusive: A=(A_1,A_2,\dots,A_N).

Snuke will perform the following operations 1 and 2 in order.

1. For each i such that A_i=0, independently choose a uniform random integer between 1 and M, inclusive, and replace A_i with that integer.
2. Sort A in ascending order.

Print the expected value of A_K after the two operations, modulo 998244353.

Constraints

• 1\leq K \leq N \leq 2000
• 1\leq M \leq 2000
• 0\leq A_i \leq M
• All values in the input are integers.

Sample Input 1

3 5 2
2 0 4

Sample Output 1

3

In the operation 1, Snuke will replace A_2 with an integer between 1 and 5. Let x be this integer.

• If x=1 or 2, we will have A_2=2 after the two operations.
• If x=3, we will have A_2=3 after the two operations.
• If x=4 or 5, we will have A_2=4 after the two operations.

Thus, the expected value of A_2 is \frac{2+2+3+4+4}{5}=3.

Sample Input 2

2 3 1
0 0

Sample Output 2

221832080

The expected value is \frac{14}{9}.

Sample Input 3

10 20 7
6 5 0 2 0 0 0 15 0 0

Sample Output 3

617586310

Problem Statement

You are given a string S consisting of digits and positive integers L and R for each of T test cases. Solve the following problem.

For a positive integer x, let us define f(x) as the number of contiguous substrings of the decimal representation of x (without leading zeros) that equal S.

For instance, if S= 22, we have f(122) = 1, f(123) = 0, f(226) = 1, and f(222) = 2.

Find \displaystyle \sum_{k=L}^{R} f(k).

Constraints

• 1 \le T \le 1000
• S is a string consisting of digits whose length is between 1 and 16, inclusive.
• L and R are integers satisfying 1 \le L \le R < 10^{16}.

Sample Input 1

6
22 23 234
0295 295 295
0 1 9999999999999999
2718 998244353 9982443530000000
869120 1234567890123456 2345678901234567
2023032520230325 1 9999999999999999

Sample Output 1

12
0
14888888888888889
12982260572545
10987664021
1

This input contains six test cases.

• In the first test case, S= 22, L=23, R=234.
  • f(122)=f(220)=f(221)=f(223)=f(224)=\dots=f(229)=1.
  • f(222)=2.
  • Thus, the answer is 12.
• In the second test case, S= 0295, L=295, R=295.
  • Note that f(295)=0.

Problem Statement

We have a directed graph G_S with N vertices numbered 1 to N. It has N-1 edges. The i-th edge (1\leq i \leq N-1) goes from vertex p_i\ (1\leq p_i \leq i) to vertex i+1.

We have another directed graph G with N vertices numbered 1 to N. Initially, G equals G_S. Process Q queries on G in the order they are given. There are two kinds of queries as follows.

• 1 u v : Add an edge to G that goes from vertex u to vertex v. It is guaranteed that the following conditions are satisfied.
  • u \neq v.
  • On G_S, vertex u is reachable from vertex v via some edges.
• 2 x : Print the smallest vertex number of a vertex reachable from vertex x via some edges on G (including vertex x).

Constraints

• 2\leq N \leq 2\times 10^5
• 1\leq Q \leq 2\times 10^5
• 1\leq p_i\leq i
• For each query in the first format:
  • 1\leq u,v \leq N.
  • u \neq v.
  • On G_S, vertex u is reachable from vertex v via some edges.
• For each query in the second format, 1\leq x \leq N.
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

4
2
1

• At the time of the first query, only vertex 4 is reachable from vertex 4 via some edges on G.
• At the time of the third query, vertices 2, 3, 4, and 5 are reachable from vertex 4 via some edges on G.
• At the time of the fifth query, vertices 1, 2, 3, 4, and 5 are reachable from vertex 4 via some edges on G.

Sample Input 2

7
1 1 2 2 3 3
10
2 5
1 5 2
2 5
1 2 1
1 7 1
1 6 3
2 5
2 6
2 1
1 7 1

Sample Output 2

5
2
1
1
1

Problem Statement

We have a grid A with N rows and M columns. Initially, 0 is written on every square.
Let us perform the following operation.

• For each integer i such that 1 \le i \le N, in the i-th row, turn the digits in zero or more leftmost squares into 1.
• For each integer j such that 1 \le j \le M, in the j-th column, turn the digits in zero or more topmost squares into 1.

Let S be the set of grids that can be obtained in this way.

You are given a grid X with N rows and M columns consisting of 0, 1, and ?.
There are 2^q grids that can be obtained by replacing each ? with 0 or 1, where q is the number of ? in X. How many of them are in S?
This count can be enormous, so find it modulo 998244353.

Constraints

• N and M are integers.
• 1 \le N,M \le 18
• X is a grid with N rows and M columns consisting of 0, 1, and ?.

Sample Input 1

2 3
0?1
?1?

Sample Output 1

6

The following six grids are in S.

011  011  001
010  011  110

001  011  011
111  110  111

Sample Input 2

5 3
101
010
101
010
101

Sample Output 2

0

X may have no ?, and the answer may be 0.

Sample Input 3

18 18
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????
??????????????????

Sample Output 3

462237431

Be sure to find the count modulo 998244353.