Problem Statement

There is a grid with 10^{100} rows and 10^{100} columns.
In what follows, the cell at the i-th row from the top and j-th column from the left is denoted as cell (i,j).

In this grid, only the 100\times 100 region with cell (P,Q) as the top-left cell is painted black, and all other cells are painted white.
Determine whether cell (X,Y) is painted black.

Constraints

• 1 \leq P,Q,X,Y \leq 10000
• P,Q,X,Y are integers.

Sample Input 1

3 3
5 10

Sample Output 1

Yes

The 100\times 100 region with cell (3,3) as the top-left cell is painted black.
Cell (5,10) is included in this region, so print Yes.

Sample Input 2

5 5
10 1000

Sample Output 2

No

The 100\times 100 region with cell (5,5) as the top-left cell is painted black.
Cell (10,1000) is not included in this region, so print No.

Sample Input 3

1 2
1 1

Sample Output 3

No

The 100\times 100 region with cell (1,2) as the top-left cell is painted black.
Cell (1,1) is not included in this region, so print No.

Problem Statement

The AtCoder country has two official languages: Takahashi-go and Aoki-go.

Both Takahashi-go and Aoki-go use some lowercase English letters to write words in those languages. Takahashi-go uses only the characters contained in a string S of length N, and Aoki-go uses only the characters contained in a string T of length M.

You are given Q words w _ 1,w _ 2,\ldots,w _ Q that are in the official languages of the AtCoder country. For each word, determine which of the following applies based on the characters contained in that word:

• It is confirmed to be a word in Takahashi-go
• It is confirmed to be a word in Aoki-go
• Neither can be determined

Constraints

• 1\le N\le26
• 1\le M\le26
• S is a string of length N consisting of lowercase English letters.
• The characters in S are arranged in alphabetical order.
• All characters in S are distinct.
• T is a string of length M consisting of lowercase English letters.
• The characters in T are arranged in alphabetical order.
• All characters in T are distinct.
• 1\le Q\le100
• w _ i is a string of length at least 1 and at most 100 consisting of lowercase English letters. (1\le i\le Q)
• w _ i is a word in Takahashi-go or Aoki-go. (1\le i\le Q)
• N,M,Q are integers.

Sample Input 1

6 5
ahikst
aikot
5
asahi
okita
kiai
hash
it

Sample Output 1

Takahashi
Aoki
Unknown
Takahashi
Unknown

For example, all of a, s, h, i are used in Takahashi-go, and h is not used in Aoki-go, so it is confirmed that asahi is a word in Takahashi-go. Thus, print Takahashi on the first line.

Both i and t are used in both Takahashi-go and Aoki-go, so it cannot be determined whether it is a word in Takahashi-go or Aoki-go. Thus, print Unknown on the fifth line.

Sample Input 2

7 6
ahiknst
ahikos
5
kioki
ohiki
tashi
nishi
kashi

Sample Output 2

Aoki
Aoki
Takahashi
Takahashi
Unknown

o is not used in Takahashi-go, so the first two words are confirmed to be words in Aoki-go. Thus, print Aoki on the first and second lines.

t and n are not used in Aoki-go, so the following two words are confirmed to be words in Takahashi-go. Thus, print Takahashi on the third and fourth lines.

For the first four words, there is a rule that words ending in shi are Takahashi-go, and words ending in ki are Aoki-go. However, all of k, a, s, h, i are used in both Takahashi-go and Aoki-go, so it is impossible to determine which language the word kashi belongs to based on the characters used. Thus, print Unknown on the fifth line.

Sample Input 3

13 11
defghiqsvwxyz
acejmoqrtwx
15
qhsqzhd
jcareec
wwqxqew
wxqxwex
jxxrtwa
trtqjxe
sqyggse
xxqwxew
xewwxxw
wwqxwex
xqqxqwq
qxxexxe
teqeroc
eeeqqee
vxdevyy

Sample Output 3

Takahashi
Aoki
Unknown
Unknown
Aoki
Aoki
Takahashi
Unknown
Unknown
Unknown
Unknown
Unknown
Aoki
Unknown
Takahashi

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

There is a directed graph (not necessarily simple) with N vertices and M edges, where the vertices are numbered as vertices 1, 2, \ldots, N.
The i-th (1\leq i\leq M) edge goes from vertex U_i to vertex V_i with cost C_i. Additionally, the out-degree of each vertex is at most 4.

Find all vertices v (1\leq v\leq N) that satisfy the following condition:

There exists a path from vertex 1 to vertex v that satisfies both of the following conditions:

• It traverses exactly L edges. If the same edge is traversed multiple times, each traversal is counted.
• The sum of the costs of the traversed edges is at least S and at most T. (If the same edge is traversed multiple times, the cost is added to the sum each time.)

Constraints

• 1\leq N\leq 2\times 10^5
• 1\leq M\leq 2\times 10^5
• 1\leq L \leq 10
• 1\leq S\leq T \leq 10^9
• 1\leq U_i,V_i\leq N
• 1\leq C_i\leq 10^8
• The out-degree of each vertex is at most 4.
• All input values are integers.

Sample Input 1

5 8 3 80 100
1 2 20
1 3 70
2 1 30
2 5 10
3 2 10
3 4 30
3 5 20
5 1 70

Sample Output 1

1 5

The given graph is as shown in the left figure below. The cost of each edge is shown near the starting vertex of that edge.

Here, the following holds:

• For the path from vertex 1 to vertex 1, consider vertex 1 \to vertex 2 \to vertex 5 \to vertex 1 (center of the figure above). This traverses exactly three edges, and the sum of the costs of the traversed edges is 20+10+70=100, so it satisfies the condition.
• There is no path from vertex 1 to vertex 2 that satisfies the condition. One path that traverses exactly three edges is vertex 1 \to vertex 2 \to vertex 1 \to vertex 2, but the sum of the costs of the edges traversed in this path is 20+30+20=70, which is less than 80, so it does not satisfy the condition.
• There is no path from vertex 1 to vertex 3 that satisfies the condition. One path that traverses exactly three edges is vertex 1 \to vertex 2 \to vertex 1 \to vertex 3, but the sum of the costs of the edges traversed in this path is 20+30+70=120, which is greater than 100, so it does not satisfy the condition.
• There is no path from vertex 1 to vertex 4 that satisfies the condition.
• For the path from vertex 1 to vertex 5, consider vertex 1 \to vertex 3 \to vertex 2 \to vertex 5 (right of the figure above). This traverses exactly three edges, and the sum of the costs of the traversed edges is 70+10+10=90, so it satisfies the condition.

Therefore, print 1, 5 in this order. Note that you need to print those vertices that satisfy the condition in ascending order.

Sample Input 2

10 1 1 1 100
2 3 1

Sample Output 2

If there are no vertices that satisfy the condition, print an empty line.

Sample Input 3

2 5 3 1 100
1 1 1
2 2 100
1 2 1
1 2 1
1 2 100

Sample Output 3

1 2

The graph may contain self-loops and multiple edges.
In this test case, the out-degrees from vertices 1 and 2 are 4 and 1, respectively.

Problem Statement

You are given a string S of length N consisting of three kinds of characters: A, B, and C.

There are \dfrac{N(N+1)}2 non-empty contiguous substrings of S. Find how many of them contain more As than Bs.

Note that two substrings are counted separately if they are taken from different positions in S, even if they are equal as strings.

Constraints

• 1\le N\le5\times10 ^ 5
• S is a string of length N consisting of A, B, and C.
• N is an integer.

Sample Input 1

10
ACBBCABCAB

Sample Output 1

8

The following eight substrings satisfy the condition:

• A: 1st to 1st character of S
• AC: 1st to 2nd character of S
• CA: 5th to 6th character of S
• CABCA: 5th to 9th character of S
• A: 6th to 6th character of S
• ABCA: 6th to 9th character of S
• CA: 8th to 9th character of S
• A: 9th to 9th character of S

All other substrings do not satisfy the condition, so print 8.

Note that A and CA can be taken from multiple positions, but they are counted separately if taken from different positions.

Sample Input 2

4
CCBC

Sample Output 2

0

There may be no substrings that satisfy the condition.

Sample Input 3

36
CABACBBBBBAABABACCBCABCCABAABABBCBAC

Sample Output 3

136

Problem Statement

A store sells N items, numbered as item 1, item 2, \ldots, item N.
Item i (1\leq i\leq N) has a price of P_i yen and a value of V_i. The store has only one stock of each item.

Takahashi chooses some items such that the total price is at most M yen.
Here, it is guaranteed that M is at least the price of any item. That is, for any 1\leq i\leq N, there exists a way to choose items such that the total price is at most M yen and item i is included.

For each 1\leq i\leq N, determine which of the following three categories item i falls into:

• Category A: To maximize the total value of the chosen items (while keeping the total price at most M yen), that item must be chosen.
• Category B: To maximize the total value of the chosen items (while keeping the total price at most M yen), that item may or may not be chosen.
• Category C: To maximize the total value of the chosen items (while keeping the total price at most M yen), that item must never be chosen.

Constraints

• 1\leq N\leq 1000
• 1\leq M\leq 5\times 10^4
• 1\leq P_i\leq M
• 1\leq V_i\leq 10^9
• All input values are integers.

Sample Input 1

5 7
2 5
2 5
3 5
3 10
3 20

Sample Output 1

BBCBA

The maximum possible total value when choosing items such that the total price is at most 7 yen is 30, which can be achieved by one of the following:

• Choosing items 1, 2, and 5.
• Choosing items 4 and 5.

(There is no other way to choose items such that the total price is at most 7 yen and the total value is 30.)
Thus, the category of each item is as follows:

• Item 5 is an item that must be chosen to maximize the total value of the chosen items (category A).
• Items 1, 2, and 4 are items that may or may not be chosen to maximize the total value of the chosen items (category B).
• Item 3 is an item that must never be chosen to maximize the total value of the chosen items (category C).

Therefore, according to the output format, print BBCBA.

Sample Input 2

7 3
1 1
1 1
1 2
1 2
1 2
1 3
1 3

Sample Output 2

CCBBBAA

The total value is maximized when choosing any one of items 3, 4, 5, along with items 6 and 7.
Note that even if items have equal prices and values, they are still distinguished as different items.

Problem Statement

N plates are arranged in a straight line from left to right. Let us call the i-th plate from the left (1\le i\le N) plate i. Initially, all plates are placed face-up, and no plates have takoyaki (octopus dumplings) on them.

Process a total of Q queries of the following three types:

• Type 1: You are given integers L,R,X. For i=L,L+1,\ldots,R, if plate i is placed face-up, place X takoyaki on plate i.
• Type 2: You are given integers L,R. For i=L,L+1,\ldots,R, if there is at least one takoyaki on plate i, eat all the takoyaki on plate i. Flip plate i (if the plate is placed face-up, place it face-down; otherwise, place it face-up).
• Type 3: You are given integers L,R. Print the maximum number of takoyaki on one plate among plates L, L+1,\ldots, R.

Constraints

• 1\le N\le2\times10 ^ 5
• 1\le Q\le2\times10 ^ 5
• In all queries, 1\le L\le R\le N.
• In type 1 queries, 1\le X\le10 ^ 9.
• There is at least one type 3 query.
• All input values are integers.

Sample Input 1

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

Sample Output 1

4
6
2

At the time of each query, the state of each plate and the number of takoyaki on it are as shown in the figure below.

At the time of the second query, among plates 2 and 3, the one with more takoyaki is plate 3. Thus, print 4, the number of takoyaki on plate 3, on the first line.

At the time of the fifth query, among plates 1, 2,\ldots, 6, the one with the most takoyaki is plate 5. Thus, print 6, the number of takoyaki on plate 5, on the second line.

At the time of the sixth query, among plates 2 and 3, the one with more takoyaki is plate 2. Thus, print 2, the number of takoyaki on plate 2, on the third line.

Sample Input 2

2 8
1 1 2 1000000000
1 1 2 1000000000
2 2 2
1 1 2 1000000000
1 1 2 1000000000
1 1 2 1000000000
3 2 2
3 1 2

Sample Output 2

0
5000000000

Note that no takoyaki is placed on plates that are placed face-down.

Also, note that the answer may be 2 ^ {32} or more.

Sample Input 3

24 30
1 11 24 4326
1 4 16 1149
1 14 20 2331
1 12 14 8930
1 22 23 6989
3 15 20
3 10 19
1 3 12 7988
1 18 23 8450
3 9 19
3 13 15
2 8 15
2 9 14
1 11 17 4062
1 6 15 1721
3 7 13
1 11 20 8541
1 8 10 3748
1 1 17 3252
2 9 23
2 1 23
3 2 22
1 5 23 7468
3 1 12
3 12 19
2 6 24
3 2 14
3 1 15
2 15 19
3 2 14

Sample Output 3

7806
16736
22393
16736
10858
0
7468
7468
0
0
0