Problem Statement

You are given a string S consisting of lowercase English letters. The length of S is between 3 and 100, inclusive.

All characters but one of S are the same.

Find x such that the x-th character of S differs from all other characters.

Constraints

• S is a string of length between 3 and 100, inclusive, consisting of two different lowercase English letters.
• All characters but one of S are the same.

Sample Input 1

yay

Sample Output 1

2

The second character of yay differs from the first and third characters.

Sample Input 2

egg

Sample Output 2

1

Sample Input 3

zzzzzwz

Sample Output 3

6

Problem Statement

The AtCoder railway line has N stations, numbered 1, 2, \ldots, N.

On this line, there are inbound trains that start at station 1 and stop at the stations 2, 3, \ldots, N in order, and outbound trains that start at station N and stop at the stations N - 1, N - 2, \ldots, 1 in order.

Takahashi is about to travel from station X to station Y using only one of the inbound and outbound trains.

Determine whether the train stops at station Z during this travel.

Constraints

• 3 \leq N \leq 100
• 1 \leq X, Y, Z \leq N
• X, Y, and Z are distinct.
• All input values are integers.

Sample Input 1

7 6 1 3

Sample Output 1

Yes

To travel from station 6 to station 1, Takahashi will take an outbound train.

After departing from station 6, the train stops at stations 5, 4, 3, 2, 1 in order, which include station 3, so you should print Yes.

Sample Input 2

10 3 2 9

Sample Output 2

No

Sample Input 3

100 23 67 45

Sample Output 3

Yes

Problem Statement

AtCoder Shop has N products. The price of the i-th product (1\leq i\leq N) is P _ i. The i-th product (1\leq i\leq N) has C_i functions. The j-th function (1\leq j\leq C _ i) of the i-th product (1\leq i\leq N) is represented as an integer F _ {i,j} between 1 and M, inclusive.

Takahashi wonders whether there is a product that is strictly superior to another. If there are i and j (1\leq i,j\leq N) such that the i-th and j-th products satisfy all of the following conditions, print Yes; otherwise, print No.

• P _ i\geq P _ j.
• The j-th product has all functions of the i-th product.
• P _ i\gt P _ j, or the j-th product has one or more functions that the i-th product lacks.

Constraints

• 2\leq N\leq100
• 1\leq M\leq100
• 1\leq P _ i\leq10^5\ (1\leq i\leq N)
• 1\leq C _ i\leq M\ (1\leq i\leq N)
• 1\leq F _ {i,1}\lt F _ {i,2}\lt\cdots\lt F _ {i,C _ i}\leq M\ (1\leq i\leq N)
• All input values are integers.

Sample Input 1

5 6
10000 2 1 3
15000 3 1 2 4
30000 3 1 3 5
35000 2 1 5
100000 6 1 2 3 4 5 6

Sample Output 1

Yes

(i,j)=(4,3) satisfies all of the conditions.

No other pair satisfies them. For instance, for (i,j)=(4,5), the j-th product has all functions of the i-th one, but P _ i\lt P _ j, so it is not strictly superior.

Sample Input 2

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

Sample Output 2

No

Multiple products may have the same price and functions.

Sample Input 3

20 10
72036 3 3 4 9
7716 4 1 2 3 6
54093 5 1 6 7 8 10
25517 7 3 4 5 6 7 9 10
96930 8 2 3 4 6 7 8 9 10
47774 6 2 4 5 6 7 9
36959 5 1 3 4 5 8
46622 7 1 2 3 5 6 8 10
34315 9 1 3 4 5 6 7 8 9 10
54129 7 1 3 4 6 7 8 9
4274 5 2 4 7 9 10
16578 5 2 3 6 7 9
61809 4 1 2 4 5
1659 5 3 5 6 9 10
59183 5 1 2 3 4 9
22186 4 3 5 6 8
98282 4 1 4 7 10
72865 8 1 2 3 4 6 8 9 10
33796 6 1 3 5 7 9 10
74670 4 1 2 6 8

Sample Output 3

Yes

Problem Statement

You are given N strings S_1,S_2,\ldots,S_N consisting of lowercase English letters.
Determine if there are distinct integers i and j between 1 and N, inclusive, such that the concatenation of S_i and S_j in this order is a palindrome.

A string T of length M is a palindrome if and only if the i-th character and the (M+1-i)-th character of T are the same for every 1\leq i\leq M.

Constraints

• 2\leq N\leq 100
• 1\leq \lvert S_i\rvert \leq 50
• N is an integer.
• S_i is a string consisting of lowercase English letters.
• All S_i are distinct.

Sample Input 1

5
ab
ccef
da
a
fe

Sample Output 1

Yes

If we take (i,j)=(1,4), the concatenation of S_1=ab and S_4=a in this order is aba, which is a palindrome, satisfying the condition.
Thus, print Yes.

Here, we can also take (i,j)=(5,2), for which the concatenation of S_5=fe and S_2=ccef in this order is feccef, satisfying the condition.

Sample Input 2

3
a
b
aba

Sample Output 2

No

No two distinct strings among S_1, S_2, and S_3 form a palindrome when concatenated. Thus, print No.
Note that the i and j in the statement must be distinct.

Sample Input 3

2
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Sample Output 3

Yes

Problem Statement

You are given N strings S_1,S_2,\dots,S_N, each of length M, consisting of lowercase English letter. Here, S_i are pairwise distinct.

Determine if one can rearrange these strings to obtain a new sequence of strings T_1,T_2,\dots,T_N such that:

• for all integers i such that 1 \le i \le N-1, one can alter exactly one character of T_i to another lowercase English letter to make it equal to T_{i+1}.

Constraints

• 2 \le N \le 8
• 1 \le M \le 5
• S_i is a string of length M consisting of lowercase English letters. (1 \le i \le N)
• S_i are pairwise distinct.

Sample Input 1

4 4
bbed
abcd
abed
fbed

Sample Output 1

Yes

One can rearrange them in this order: abcd, abed, bbed, fbed. This sequence satisfies the condition.

Sample Input 2

2 5
abcde
abced

Sample Output 2

No

No matter how the strings are rearranged, the condition is never satisfied.

Sample Input 3

8 4
fast
face
cast
race
fact
rice
nice
case

Sample Output 3

Yes

Problem Statement

You are given a sequence A=(A_1,A_2,\dots,A_{3N}) of length 3N where each of 1,2,\dots, and N occurs exactly three times.

For i=1,2,\dots,N, let f(i) be the index of the middle occurrence of i in A. Sort 1,2,\dots,N in ascending order of f(i).

Formally, f(i) is defined as follows.

• Suppose that those j such that A_j = i are j=\alpha,\beta,\gamma\ (\alpha < \beta < \gamma). Then, f(i) = \beta.

Constraints

• 1\leq N \leq 10^5
• 1 \leq A_j \leq N
• i occurs in A exactly three times, for each i=1,2,\dots,N.
• All input values are integers.

Sample Input 1

3
1 1 3 2 3 2 2 3 1

Sample Output 1

1 3 2

• 1 occurs in A at A_1,A_2,A_9, so f(1) = 2.
• 2 occurs in A at A_4,A_6,A_7, so f(2) = 6.
• 3 occurs in A at A_3,A_5,A_8, so f(3) = 5.

Thus, f(1) < f(3) < f(2), so 1,3, and 2 should be printed in this order.

Sample Input 2

1
1 1 1

Sample Output 2

1

Sample Input 3

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

Sample Output 3

3 4 1 2

Problem Statement

We have a string S. Initially, S= 1.
Process Q queries in the following formats in order.

• 1 x : Append a digit x at the end of S.
• 2 : Delete the digit at the beginning of S.
• 3 : Print the number represented by S in decimal, modulo 998244353.

Constraints

• 1 \leq Q \leq 6 \times 10^5
• For each query in the first format, x \in \{1,2,3,4,5,6,7,8,9\}.
• A query in the second format is given only if S has a length of 2 or greater.
• There is at least one query in the third format.

Sample Input 1

3
3
1 2
3

Sample Output 1

1
12

In the first query, S is 1, so you should print 1 modulo 998244353, that is, 1.
In the second query, S becomes 12.
In the third query, S is 12, so you should print 12 modulo 998244353, that is, 12.

Sample Input 2

3
1 5
2
3

Sample Output 2

5

Sample Input 3

11
1 9
1 9
1 8
1 2
1 4
1 4
1 3
1 5
1 3
2
3

Sample Output 3

0

Be sure to print numbers modulo 998244353.

Problem Statement

You are given a simple directed graph with N vertices numbered 1 to N and M edges numbered 1 to M. Edge i is a directed edge from vertex u_i to vertex v_i.

You may perform the following operation zero or more times.

• Choose distinct vertices x and y such that there is no directed edge from vertex x to vertex y, and add a directed edge from vertex x to vertex y.

Find the minimum number of times you need to perform the operation to make the graph satisfy the following condition.

• For every triple of distinct vertices a, b, and c, if there are directed edges from vertex a to vertex b and from vertex b to vertex c, there is also a directed edge from vertex a to vertex c.

Constraints

• 3 \leq N \leq 2000
• 0 \leq M \leq 2000
• 1 \leq u_i ,v_i \leq N
• u_i \neq v_i
• (u_i,v_i) \neq (u_j,v_j) if i \neq j.
• All values in the input are integers.

Sample Input 1

4 3
2 4
3 1
4 3

Sample Output 1

3

Initially, the condition is not satisfied because, for instance, for vertices 2, 4, and 3, there are directed edges from vertex 2 to vertex 4 and from vertex 4 to vertex 3, but not from vertex 2 to vertex 3.

You can make the graph satisfy the condition by adding the following three directed edges:

• one from vertex 2 to vertex 3,
• one from vertex 2 to vertex 1, and
• one from vertex 4 to vertex 1.

On the other hand, the condition cannot be satisfied by adding two or fewer edges, so the answer is 3.

Sample Input 2

292 0

Sample Output 2

0

Sample Input 3

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

Sample Output 3

12

Problem Statement

You are given a positive integer N and sequences of N positive integers each: A=(A_1,A_2,\dots,A_N) and B=(B_1,B_2,\dots,B_N).

We have an N \times N grid. The square at the i-th row from the top and the j-th column from the left is called the square (i,j). For each pair of integers (i,j) such that 1 \le i,j \le N, the square (i,j) has the integer A_i + B_j written on it. Process Q queries of the following form.

• You are given a quadruple of integers h_1,h_2,w_1,w_2 such that 1 \le h_1 \le h_2 \le N,1 \le w_1 \le w_2 \le N. Find the greatest common divisor of the integers contained in the rectangle region whose top-left and bottom-right corners are (h_1,w_1) and (h_2,w_2), respectively.

Constraints

• 1 \le N,Q \le 2 \times 10^5
• 1 \le A_i,B_i \le 10^9
• 1 \le h_1 \le h_2 \le N
• 1 \le w_1 \le w_2 \le N
• All values in input are integers.

Sample Input 1

3 5
3 5 2
8 1 3
1 2 2 3
1 3 1 3
1 1 1 1
2 2 2 2
3 3 1 1

Sample Output 1

2
1
11
6
10

Let C_{i,j} denote the integer on the square (i,j).

For the 1-st query, we have C_{1,2}=4,C_{1,3}=6,C_{2,2}=6,C_{2,3}=8, so the answer is their greatest common divisor, which is 2.

Sample Input 2

1 1
9
100
1 1 1 1

Sample Output 2

109