Problem Statement

There are N items. You are given strings T and A of length N that represent which items Takahashi and Aoki want, respectively. Let T_i and A_i be the i-th (1\leq i\leq N) characters of T and A, respectively.

Takahashi wants the i-th item when T_i is o, and does not want the i-th item when T_i is x. Similarly, Aoki wants the i-th item when A_i is o, and does not want the i-th item when A_i is x.

Determine whether there exists an item that both of them want.

Constraints

• 1\leq N\leq 100
• N is an integer.
• T and A are strings of length N consisting of o and x.

Sample Input 1

4
oxoo
xoox

Sample Output 1

Yes

The third item is wanted by both of them, so output Yes.

Sample Input 2

5
xxxxx
ooooo

Sample Output 2

No

There is no item that both of them want, so output No.

Sample Input 3

10
xoooxoxxxo
ooxooooxoo

Sample Output 3

Yes

Problem Statement

Given integers a, b, and c, determine if b is the median of these integers.

Constraints

• 1 \leq a, b, c \leq 100
• All values in input are integers.

Sample Input 1

5 3 2

Sample Output 1

Yes

The given integers are 2, 3, 5 when sorted in ascending order, of which b is the median.

Sample Input 2

2 5 3

Sample Output 2

No

b is not the median of the given integers.

Sample Input 3

100 100 100

Sample Output 3

Yes

Problem Statement

N woodcutters 1, 2, \dots, N each have one axe. All of them dropped their axes into a pond.
N axes 1, 2, \dots, N were found sunk in the pond.
Each woodcutter i claims that "I owned axe A_i."
On the other hand, the goddess of this pond knows that the woodcutter who owned axe i is woodcutter B_i.

Determine whether all N woodcutters are telling the truth.

Constraints

• 1 \leq N \leq 100
• 1 \leq A_i \leq N
• 1 \leq B_i \leq N
• A_i \neq A_j\;(i \neq j)
• B_i \neq B_j\;(i \neq j)
• All input values are integers.

Sample Input 1

3
3 1 2
2 3 1

Sample Output 1

Yes

All N woodcutters are telling the truth.

Sample Input 2

4
1 2 3 4
1 3 2 4

Sample Output 2

No

Woodcutters 2 and 3 are lying.

Sample Input 3

5
2 4 5 1 3
4 1 5 2 3

Sample Output 3

Yes

Problem Statement

You are given strings S and T consisting of lowercase and uppercase English letters.

Determine whether the string S satisfies the following condition:

• Every uppercase letter in S that is not at the beginning is immediately preceded by a character contained in T. More formally, for all integers i such that 2 \leq i \leq |S|, if the i-th character of S is uppercase, then the (i-1)-th character of S is contained in T.

Constraints

• Each of S and T is a string consisting of lowercase and uppercase English letters with length between 1 and 100, inclusive.

Sample Input 1

AtCoder
Total

Sample Output 1

Yes

The only uppercase letter in S that is not at the beginning is the 3rd character C. The immediately preceding character t is contained in T, so output Yes.

Sample Input 2

aBCdE
abcdcba

Sample Output 2

No

The 3rd character of S is the uppercase letter C, and its immediately preceding character is B, but B is not contained in T.

Sample Input 3

abcde
XYZ

Sample Output 3

Yes

Problem Statement

There are N cups, each containing a colorless and transparent liquid.
Specifically, the i-th (1\leq i\leq N) cup contains A_i ml of liquid.
It is known that exactly K of these cups contain sake (rice wine), and the rest contain water.
However, it is not known which cups contain sake.

Takahashi can choose some (one or more) cups and drink all the liquid in them.
Find the minimum number of cups he needs to choose to ensure he drinks at least X ml of sake, regardless of which cups contain sake.
If such a choice is impossible, print -1.

Constraints

• 1 \leq K \leq N \leq 3\times 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq X \leq 3\times 10^{14}
• All input values are integers.

Sample Input 1

3 2 5
10 6 8

Sample Output 1

2

Consider the case where Takahashi chooses the first and third cups and drinks them.

Two out of the three cups contain sake, so the following three cases are possible:

• If the first and second cups contain sake

He drinks 10 ml of sake and 8 ml of water.

• If the first and third cups contain sake

He drinks 18 ml of sake.

• If the second and third cups contain sake

He drinks 8 ml of sake and 10 ml of water.

Thus, in all cases, he can drink at least 5 ml of sake.
On the other hand, it is impossible to satisfy the condition by choosing only one cup without knowing which cups contain sake.

Therefore, print 2.

Sample Input 2

2 1 8
6 10

Sample Output 2

-1

If the first cup contained sake, it is impossible to drink 8 ml or more of sake no matter which cups are chosen.
Therefore, print -1.

Sample Input 3

5 3 3000000000
1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

5

Problem Statement

N students are taking a 4-day exam.

There is a 300-point test on each day, for a total of 1200 points.

The first three days of the exam are already over, and the fourth day is now about to begin. The i-th student (1 \leq i \leq N) got P_{i, j} points on the j-th day (1 \leq j \leq 3).

For each student, determine whether it is possible that he/she is ranked in the top K after the fourth day.
Here, the rank of a student after the fourth day is defined as the number of students whose total scores over the four days are higher than that of the student, plus 1.

Constraints

• 1 \leq K \leq N \leq 10^5
• 0 \leq P_{i, j} \leq 300 \, (1 \leq i \leq N, 1 \leq j \leq 3)
• All values in input are integers.

Sample Input 1

3 1
178 205 132
112 220 96
36 64 20

Sample Output 1

Yes
Yes
No

If every student scores 100 on the fourth day, the 1-st student will rank 1-st.
If the 2-nd student scores 100 and the other students score 0 on the fourth day, the 2-nd student will rank 1-st.
The 3-rd student will never rank 1-st.

Sample Input 2

2 1
300 300 300
200 200 200

Sample Output 2

Yes
Yes

Sample Input 3

4 2
127 235 78
192 134 298
28 56 42
96 120 250

Sample Output 3

Yes
Yes
No
Yes

Problem Statement

There are N buildings, Building 1, Building 2, \ldots, Building N, arranged in a line in this order. The height of Building i (1 \leq i \leq N) is H_i.

For each i = 1, 2, \ldots, N, find the number of integers j (i < j \leq N) satisfying the following condition:

• There is no building taller than Building j between Buildings i and j.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq H_i \leq N
• H_i\neq H_j\ (i\neq j)
• All input values are integers.

Sample Input 1

5
2 1 4 3 5

Sample Output 1

3 2 2 1 0

For i=1, the integers j satisfying the condition are 2, 3, and 5: there are three. (Between Buildings 1 and 4, there is a building taller than Building 4, which is Building 3, so j=4 does not satisfy the condition.) Therefore, the first number in the output is 3.

Sample Input 2

4
1 2 3 4

Sample Output 2

3 2 1 0

Sample Input 3

10
1 9 6 5 2 7 10 4 8 3

Sample Output 3

2 3 3 3 2 1 2 1 1 0

Problem Statement

There are N integers a_1,\ldots,a_N written on a whiteboard.
Here, a_i can be represented as a_i = p_{i,1}^{e_{i,1}} \times \ldots \times p_{i,m_i}^{e_{i,m_i}} using m_i prime numbers p_{i,1} \lt \ldots \lt p_{i,m_i} and positive integers e_{i,1},\ldots,e_{i,m_i}.
You will choose one of the N integers to replace it with 1.
Find the number of values that can be the least common multiple of the N integers after the replacement.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq m_i
• \sum{m_i} \leq 2 \times 10^5
• 2 \leq p_{i,1} \lt \ldots \lt p_{i,m_i} \leq 10^9
• p_{i,j} is prime.
• 1 \leq e_{i,j} \leq 10^9
• All values in input are integers.

Sample Input 1

4
1
7 2
2
2 2
5 1
1
5 1
2
2 1
7 1

Sample Output 1

3

The integers on the whiteboard are a_1 =7^2=49, a_2=2^2 \times 5^1 = 20, a_3 = 5^1 = 5, a_4=2^1 \times 7^1 = 14.
If you replace a_1 with 1, the integers on the whiteboard become 1,20,5,14, whose least common multiple is 140.
If you replace a_2 with 1, the integers on the whiteboard become 49,1,5,14, whose least common multiple is 490.
If you replace a_3 with 1, the integers on the whiteboard become 49,20,1,14, whose least common multiple is 980.
If you replace a_4 with 1, the integers on the whiteboard become 49,20,5,1, whose least common multiple is 980.
Therefore, the least common multiple of the N integers after the replacement can be 140, 490, or 980, so the answer is 3.

Sample Input 2

1
1
998244353 1000000000

Sample Output 2

1

There may be enormous integers on the whiteboard.

Problem Statement

You are given a grid with three rows and N columns. Denote the cell at the i-th row from the top and j-th column from the left as cell (i,j). Cell (i,j) is a wall cell if S_{i,j} is #, and an empty cell and passable if it is ..

You are given Q queries, which you should process in order.

Each query gives integers r and c, and you should flip the state of cell (r,c). That is, if cell (r,c) is a wall cell, make it an empty cell, and if it is an empty cell, make it a wall cell. Then, output the answer to the following problem:

Consider moving from cell (1,1) to cell (3,N) by repeatedly moving to an empty cell adjacent up, down, left, or right. Determine whether cell (3,N) is reachable, and if reachable, find the minimum number of moves.

Constraints

• 2\le N\le 2\times 10^5
• S_{i,j} is # or ..
• S_{1,1}=S_{3,N}= .
• 1\le Q\le 2\times 10^5
• 1\le r\le 3
• 1\le c\le N
• (r,c) \neq (1,1),(3,N)
• N,Q,r,c are integers.

Sample Input 1

5
.#...
.#.#.
...#.
3
1 2
1 2
2 3

Sample Output 1

6
10
-1

In the first query, flip the state of cell (1,2). As a result, the state of each cell becomes:

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

At this time, by moving from cell (1,1) through cells (1,2),(1,3),(1,4),(1,5),(2,5),(3,5) in order, you can reach cell (3,5) in six moves.

In the second query, flip the state of cell (1,2). As a result, the state of each cell becomes:

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

At this time, by moving from cell (1,1) through cells (2,1),(3,1),(3,2),(3,3),(2,3),(1,3),(1,4),(1,5),(2,5),(3,5) in order, you can reach cell (3,5) in ten moves.

In the third query, flip the state of cell (2,3). As a result, the state of each cell becomes:

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

At this time, no matter how you move, you cannot reach cell (3,5) from cell (1,1).

Sample Input 2

7
.#.....
.#..#..
...#...
6
2 5
3 4
3 5
2 5
1 4
1 4

Sample Output 2

10
8
10
12
-1
12