Problem Statement

There are N people. Each of them agrees or disagrees with a proposal. Here, N is an odd number.

The i-th (i = 1, 2, \dots, N) person's opinion is represented by a string S_i: the person agrees if S_i = For and disagrees if S_i = Against.

Determine whether the majority agrees with the proposal.

Constraints

• N is an odd number between 1 and 99, inclusive.
• S_i = For or S_i = Against, for all i = 1, 2, \dots, N.

Sample Input 1

3
For
Against
For

Sample Output 1

Yes

The proposal is supported by two people, which is the majority, so Yes should be printed.

Sample Input 2

5
Against
Against
For
Against
For

Sample Output 2

No

The proposal is supported by two people, which is not the majority, so No should be printed.

Sample Input 3

1
For

Sample Output 3

Yes

Problem Statement

You are given N strings of length six each, consisting of digits. Let S_i be the i-th (i = 1, 2, \dots, N) of them.

You are also given M strings of length three each, consisting of digits. Let T_j be the j-th (j = 1, 2, \dots, M) of them.

Find the number of strings among S_1, S_2, \dots, S_N whose last three characters coincide with one or more of T_1, T_2, \dots, T_M.

Constraints

• 1 \leq N, M \leq 1000
• N and M are integers.
• S_i is a string of length 6 consisting of digits, for all i = 1, 2, \dots, N.
• T_j is a string of length 3 consisting of digits, for all j = 1, 2, \dots, M.

Sample Input 1

3 3
142857
004159
071028
159
287
857

Sample Output 1

2

The last three characters of S_1 are 857, which coincide with T_3.
The last three characters of S_2 are 159, which coincide with T_1.
The last three characters of S_3 are 028, which do not coincide with T_1, T_2, or T_3.

Thus, the answer is 2.

Sample Input 2

5 4
235983
109467
823476
592801
000333
333
108
467
983

Sample Output 2

3

Sample Input 3

4 4
000000
123456
987111
000000
000
111
999
111

Sample Output 3

3

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1, 2, \dots, N, and the edges are numbered 1, 2, \dots, M.
Edge i \, (i = 1, 2, \dots, M) connects vertices u_i and v_i.

Determine if this graph is a path graph.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq u_i, v_i \leq N \, (i = 1, 2, \dots, M)
• All values in the input are integers.
• The graph given in the input is simple.

Sample Input 1

4 3
1 3
4 2
3 2

Sample Output 1

Yes

Illustrated below is the given graph, which is a path graph.

Sample Input 2

2 0

Sample Output 2

No

Illustrated below is the given graph, which is not a path graph.

Sample Input 3

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

Sample Output 3

No

Illustrated below is the given graph, which is not a path graph.

Problem Statement

You are given strings S and T consisting of lowercase English letters and ?. Here, |S| \gt |T| holds (for a string X, |X| denotes the length of X).

Two strings X and Y such that |X|=|Y| is said to match if and only if:

• one can make X equal Y by replacing each ? in X and Y with any English letter independently.

Solve the following problem for each x=0,1,\ldots,|T|:

• Let S' be the string of length |T| obtained by concatenating the first x characters and the last (|T|-x) characters of S without changing the order. Print Yes if S' and T match, and No otherwise.

Constraints

• S and T are strings consisting of lowercase English letters and ?.
• 1 \leq |T| \lt |S| \leq 3 \times 10^5

Sample Input 1

a?c
b?

Sample Output 1

Yes
No
No

When x=0, S' equals ?c. Here, we can replace the 1-st character of S', ?, with b and the 2-nd character of T, ?, with c to make S' equal T, so S' and T match. Thus, Yes should be printed in the first line.
When x=1 and 2, respectively, S' is ac and a?, neither of which matches with T. Thus, No should be printed in the second and third lines.

Sample Input 2

atcoder
?????

Sample Output 2

Yes
Yes
Yes
Yes
Yes
Yes

Sample Input 3

beginner
contest

Sample Output 3

No
No
No
No
No
No
No
No

Problem Statement

You are given N strings consisting of lowercase English letters. Let S_i be the i-th (i = 1, 2, \dots, N) of them.

For two strings x and y, \mathrm{LCP}(x, y) is defined to be the maximum integer n that satisfies all of the following conditions:

• The lengths of x and y are both at least n.
• For all integers i between 1 and n, inclusive, the i-th character of x and that of y are equal.

Find the following value for all i = 1, 2, \dots, N:

• \displaystyle \max_{i \neq j} \mathrm{LCP}(S_i, S_j)

Constraints

• 2 \leq N \leq 5 \times 10^5
• N is an integer.
• S_i is a string of length at least 1 consisting of lowercase English letters (i = 1, 2, \dots, N).
• The sum of lengths of S_i is at most 5 \times 10^5.

Sample Input 1

3
abc
abb
aac

Sample Output 1

2
2
1

\mathrm{LCP}(S_1, S_2) = 2, \mathrm{LCP}(S_1, S_3) = 1, and \mathrm{LCP}(S_2, S_3) = 1.

Sample Input 2

11
abracadabra
bracadabra
racadabra
acadabra
cadabra
adabra
dabra
abra
bra
ra
a

Sample Output 2

4
3
2
1
0
1
0
4
3
2
1

Problem Statement

You are given a tree with N vertices. The vertices are numbered 1 through N, and the i-th edge connects vertex a_i and vertex b_i.

Solve the following problem for each x=1,2,\ldots,N:

• There are (2^N-1) non-empty subsets V of the tree's vertices. Find the number, modulo 998244353, of such V that the subgraph induced by V has exactly x connected components.

Constraints

• 1 \leq N \leq 5000
• 1 \leq a_i \lt b_i \leq N
• The given graph is a tree.

Sample Input 1

4
1 2
2 3
3 4

Sample Output 1

10
5
0
0

The induced subgraph will have two connected components in the following five cases and one in the others.

• V = \{1,2,4\}
• V = \{1,3\}
• V = \{1,3,4\}
• V = \{1,4\}
• V = \{2,4\}

Sample Input 2

2
1 2

Sample Output 2

3
0

Sample Input 3

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

Sample Output 3

140
281
352
195
52
3
0
0
0
0

Problem Statement

Takahashi has 10^{100} cards of each of N kinds. Initially, the score and quota of the i-th kind of card are set to a_i and b_i, respectively.

Given Q queries in the following formats, process them in order.

• 1 x y: set the score of the x-th kind of card to y.
• 2 x y: set the quota of the x-th kind of card to y.
• 3 x: if one can choose x cards subject to the following condition, print the maximum possible sum of the scores of the chosen cards; print -1 otherwise.
  • The number of chosen cards of each kind does not exceed its quota.

Constraints

• 1 \leq N,Q \leq 2 \times 10^5
• 0 \leq a_i \leq 10^9
• 0 \leq b_i \leq 10^4
• For each query of the 1-st kind, 1 \leq x \leq N and 0 \leq y \leq 10^9.
• For each query of the 2-nd kind, 1 \leq x \leq N and 0 \leq y \leq 10^4.
• For each query of the 3-rd kind, 1 \leq x \leq 10^9.
• There is at least one query of the 3-rd kind.
• All values in the input are integers.

Sample Input 1

3
1 1
2 2
3 3
7
3 4
1 1 10
3 4
2 1 0
2 3 0
3 4
3 2

Sample Output 1

11
19
-1
4

For the first query of the 3-rd kind, you can choose one card of the 2-nd kind and three cards of the 3-rd kind for a total score of 11, which is the maximum.
For the second such query, you can choose one card of the 1-st kind and three cards of the 3-rd kind for a total score of 19, which is the maximum.
For the third such query, you cannot choose four cards, so -1 should be printed.
For the fourth such query, you can choose two cards of the 2-nd kind for a total score of 4, which is the maximum.

Problem Statement

There is a directed graph with N vertices and M edges. The vertices are numbered 1 through N, and the i-th directed edge goes from vertex a_i to vertex b_i.

The cost of a path on this graph is defined as:

• the maximum index of a vertex on the path (including the initial and final vertices).

Solve the following problem for each x=1,2,\ldots,Q.

• Find the minimum cost of a path from vertex s_x to vertex t_x. If there is no such path, print -1 instead.

The use of fast input and output methods is recommended because of potentially large input and output.

Constraints

• 2 \leq N \leq 2000
• 0 \leq M \leq N(N-1)
• 1 \leq a_i,b_i \leq N
• a_i \neq b_i
• If i \neq j, then (a_i,b_i) \neq (a_j,b_j).
• 1 \leq Q \leq 10^4
• 1 \leq s_i,t_i \leq N
• s_i \neq t_i
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

2
3
-1

For x=1, the path via the 1-st edge from vertex 1 to vertex 2 has a cost of 2, which is the minimum.
For x=2, the path via the 2-nd edge from vertex 2 to vertex 3 and then via the 3-rd edge from vertex 3 to vertex 1 has a cost of 3, which is the minimum.
For x=3, there is no path from vertex 1 to vertex 4, so -1 should be printed.