Problem Statement

You are given a string S consisting of v and w.

Print the number of "bottoms" in the string S (see the figure at Sample Input/Output).

Constraints

• S is a string consisting of v and w.
• The length of S is between 1 and 100, inclusive.

Sample Input 1

vvwvw

Sample Output 1

7

The image above shows the seven "bottoms" in the string vvwvw.

Sample Input 2

v

Sample Output 2

1

Sample Input 3

wwwvvvvvv

Sample Output 3

12

Problem Statement

The ASCII values of the lowercase English letters a, b, \ldots, z are 97,98,\ldots,122 in this order.

Given an integer N between 97 and 122, print the letter whose ASCII value is N.

Constraints

• N is an integer between 97 and 122 (inclusive).

Sample Input 1

97

Sample Output 1

a

97 is the ASCII value of a.

Sample Input 2

122

Sample Output 2

z

Problem Statement

N players, who are numbered 1, \ldots, N, have played a game. Player i has scored A_i, and a player with a smaller score ranks higher.

The player who ranks the second lowest will receive a booby prize. Who is this player? Answer with an integer representing the player.

Constraints

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

Sample Input 1

6
1 123 12345 12 1234 123456

Sample Output 1

3

It is Player 3 who ranks fifth among the six players.

Sample Input 2

5
3 1 4 15 9

Sample Output 2

5

Problem Statement

Let us call a string consisting of uppercase and lowercase English alphabets a wonderful string if all of the following conditions are satisfied:

• The string contains an uppercase English alphabet.
• The string contains a lowercase English alphabet.
• All characters in the string are pairwise distinct.

For example, AtCoder and Aa are wonderful strings, while atcoder and Perfect are not.

Given a string S, determine if S is a wonderful string.

Constraints

• 1 \le |S| \le 100
• S is a string consisting of uppercase and lowercase English alphabets.

Sample Input 1

AtCoder

Sample Output 1

Yes

AtCoder is a wonderful string because it contains an uppercase English alphabet, a lowercase English alphabet, and all characters in the string are pairwise distinct.

Sample Input 2

Aa

Sample Output 2

Yes

Note that A and a are different characters. This string is a wonderful string.

Sample Input 3

atcoder

Sample Output 3

No

It is not a wonderful string because it does not contain an uppercase English alphabet.

Sample Input 4

Perfect

Sample Output 4

No

It is not a wonderful string because the 2-nd and the 5-th characters are the same.

Problem Statement

Snuke the doctor prescribed N kinds of medicine for Takahashi. For the next a_i days (including the day of the prescription), he has to take b_i pills of the i-th medicine. He does not have to take any other medicine.

Let the day of the prescription be day 1. On or after day 1, when is the first day on which he has to take K pills or less?

Constraints

• 1 \leq N \leq 3 \times 10^5
• 0 \leq K \leq 10^9
• 1 \leq a_i,b_i \leq 10^9
• All input values are integers.

Sample Input 1

4 8
6 3
2 5
1 9
4 2

Sample Output 1

3

On day 1, he has to take 3,5,9, and 2 pills of the 1-st, 2-nd, 3-rd, and 4-th medicine, respectively. In total, he has to take 19 pills on this day, which is not K(=8) pills or less.
On day 2, he has to take 3,5, and 2 pills of the 1-st, 2-nd, and 4-th medicine, respectively. In total, he has to take 10 pills on this day, which is not K(=8) pills or less.
On day 3, he has to take 3 and 2 pills of the 1-st and 4-th medicine, respectively. In total, he has to take 5 pills on this day, which is K(=8) pills or less for the first time.

Thus, the answer is 3.

Sample Input 2

4 100
6 3
2 5
1 9
4 2

Sample Output 2

1

Sample Input 3

15 158260522
877914575 2436426
24979445 61648772
623690081 33933447
476190629 62703497
211047202 71407775
628894325 31963982
822804784 50968417
430302156 82631932
161735902 80895728
923078537 7723857
189330739 10286918
802329211 4539679
303238506 17063340
492686568 73361868
125660016 50287940

Sample Output 3

492686569

Problem Statement

Poem Online Judge (POJ) is an online judge that gives scores to submitted strings.
There were N submissions to POJ. In the i-th earliest submission, string S_i was submitted, and a score of T_i was given. (The same string may have been submitted multiple times.)
Note that POJ may not necessarily give the same score to submissions with the same string.

A submission is said to be an original submission if the string in the submission is never submitted in any earlier submission.
A submission is said to be the best submission if it is an original submission with the highest score. If there are multiple such submissions, only the earliest one is considered the best submission.

Find the index of the best submission.

Constraints

• 1 \leq N \leq 10^5
• S_i is a string consisting of lowercase English characters.
• S_i has a length between 1 and 10, inclusive.
• 0 \leq T_i \leq 10^9
• N and T_i are integers.

Sample Input 1

3
aaa 10
bbb 20
aaa 30

Sample Output 1

2

We will refer to the i-th earliest submission as Submission i.
Original submissions are Submissions 1 and 2. Submission 3 is not original because it has the same string as that in Submission 1.
Among the original submissions, Submission 2 has the highest score. Therefore, this is the best submission.

Sample Input 2

5
aaa 9
bbb 10
ccc 10
ddd 10
bbb 11

Sample Output 2

2

Original submissions are Submissions 1, 2, 3, and 4.
Among them, Submissions 2, 3, and 4 have the highest scores. In this case, the earliest submission among them, Submission 2, is the best.
As in this sample, beware that if multiple original submissions have the highest scores, only the one with the earliest among them is considered the best submission.

Sample Input 3

10
bb 3
ba 1
aa 4
bb 1
ba 5
aa 9
aa 2
ab 6
bb 5
ab 3

Sample Output 3

8

Problem Statement

Takahashi is displaying a sentence with N words in a window. All words have the same height, and the width of the i-th word (1\leq i\leq N) is L _ i.

The words are displayed in the window separated by a space of width 1. More precisely, when the sentence is displayed in a window of width W, the following conditions are satisfied.

• The sentence is divided into several lines.
• The first word is displayed at the beginning of the top line.
• The i-th word (2\leq i\leq N) is displayed either with a gap of 1 after the (i-1)-th word, or at the beginning of the line below the line containing the (i-1)-th word. It will not be displayed anywhere else.
• The width of each line does not exceed W. Here, the width of a line refers to the distance from the left end of the leftmost word to the right end of the rightmost word.

When Takahashi displayed the sentence in the window, the sentence fit into M or fewer lines. Find the minimum possible width of the window.

Constraints

• 1\leq M\leq N\leq2\times10 ^ 5
• 1\leq L _ i\leq10^9\ (1\leq i\leq N)
• All input values are integers.

Sample Input 1

13 3
9 5 2 7 1 8 8 2 1 5 2 3 6

Sample Output 1

26

When the width of the window is 26, you can fit the given sentence into three lines as follows.

You cannot fit the given sentence into three lines when the width of the window is 25 or less, so print 26.

Note that you should not display a word across multiple lines, let the width of a line exceed the width of the window, or rearrange the words.

Sample Input 2

10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 2

10000000009

Note that the answer may not fit into a 32\operatorname{bit} integer.

Sample Input 3

30 8
8 55 26 97 48 37 47 35 55 5 17 62 2 60 23 99 73 34 75 7 46 82 84 29 41 32 31 52 32 60

Sample Output 3

189

Problem Statement

There is an undirected graph with N vertices and 0 edges. The vertices are numbered 1 to N.

You are given Q queries to process in order. Each query is of one of the following two types:

• Type 1: Given in the format 1 u v. Add an edge between vertices u and v.
• Type 2: Given in the format 2 v k. Print the k-th largest vertex number among the vertices connected to vertex v. If there are fewer than k vertices connected to v, print -1.

Constraints

• 1 \leq N, Q \leq 2 \times 10^5
• In a Type 1 query, 1 \leq u < v \leq N.
• In a Type 2 query, 1 \leq v \leq N, 1 \leq k \leq 10.
• All input values are integers.

Sample Input 1

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

Sample Output 1

2
1
-1
4
2
-1

• In the first query, an edge is added between vertices 1 and 2.
• In the second query, two vertices are connected to vertex 1: 1 and 2. Among them, the 1-st largest vertex number is 2, which should be printed.
• In the third query, two vertices are connected to vertex 1: 1 and 2. Among them, the 2-nd largest vertex number is 1, which should be printed.
• In the fourth query, two vertices are connected to vertex 1: 1 and 2, which is fewer than 3, so print -1.
• In the fifth query, an edge is added between vertices 1 and 3.
• In the sixth query, an edge is added between vertices 2 and 3.
• In the seventh query, an edge is added between vertices 3 and 4.
• In the eighth query, four vertices are connected to vertex 1: 1,2,3,4. Among them, the 1-st largest vertex number is 4, which should be printed.
• In the ninth query, four vertices are connected to vertex 1: 1,2,3,4. Among them, the 3-rd largest vertex number is 2, which should be printed.
• In the tenth query, four vertices are connected to vertex 1: 1,2,3,4, which is fewer than 5, so print -1.

Sample Input 2

6 20
1 3 4
1 3 5
2 1 1
2 3 1
1 1 5
2 6 9
2 1 3
2 6 1
1 4 6
2 2 1
2 6 2
2 4 7
1 1 4
2 6 2
2 3 4
1 2 5
2 4 1
1 1 6
2 3 3
2 1 3

Sample Output 2

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

Problem Statement

Snuke is planning to build a maze as a new attraction in AtCoder Land. The maze is represented as a grid with N rows and M columns, with the top edge of the top-right cell being the entrance and the bottom edge of the bottom-right cell being the exit. He will create the maze by appropriately placing walls between adjacent cells.

He loves simple mazes, so he wants the path from the entrance to the exit to pass through exactly K cells without any branches. Determine if it is possible to create such a maze, and if possible, construct one.

For example, in the following figure, N=3 and M=3, and walls are placed at the solid lines (walls are always placed around the outer perimeter except for the entrance and exit). In this case, the path from the entrance to the exit passes through exactly 7 cells without any branches.

Below is a formal statement.

There is a grid with N rows and M columns. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left. For each pair of side-adjacent cells, you can decide whether to place a wall between them. Determine whether it is possible to place walls to satisfy the following condition, and if it is possible, construct one such placement.

Consider an undirected graph G with NM vertices. Each vertex of G is uniquely labeled by a pair of integers (i,j)\ (1\leq i\leq N, 1\leq j\leq M). Two distinct vertices (i_1,j_1) and (i_2,j_2) are connected by an edge if and only if |i_1-i_2|+|j_1-j_2|=1 and there is no wall between the corresponding cells (i_1,j_1) and (i_2,j_2) on the grid.

Condition: there exists a simple path with K vertices that connects the two vertices (1,M) and (N,M), and the connected component containing the vertices (1,M) and (N,M) consists only of this path.

Constraints

• 2\leq N \leq 100
• 1\leq M \leq 100
• 1\leq K\leq NM
• All input values are integers.

Sample Input 1

3 3 7

Sample Output 1

Yes
+++++S+
+o.o.o+
+.+-+-+
+o.o.o+
+-+-+.+
+o.o|o+
+++++G+

This is the same placement of walls as in the figure in the problem statement.

Sample Input 2

3 3 2

Sample Output 2

No

Sample Input 3

4 1 4

Sample Output 3

Yes
+S+
+o+
+.+
+o+
+.+
+o+
+.+
+o+
+G+