Problem Statement

You are given an integer N between 1 and 9, inclusive, as input.

Concatenate N copies of the digit N and print the resulting string.

Constraints

• N is an integer between 1 and 9, inclusive.

Sample Input 1

3

Sample Output 1

333

Concatenate three copies of the digit 3 to yield the string 333.

Sample Input 2

9

Sample Output 2

999999999

Problem Statement

Takahashi wants a beverage called AtCoder Drink in a restaurant. It can be ordered at a regular price of P yen.

He also has a discount coupon that allows him to order it at a lower price of Q yen. However, he must additionally order one of the restaurant's N dishes to use that coupon. For each i = 1, 2, \ldots, N, the price of the i-th dish is D_i yen.

Print the minimum total amount of money that he must pay to get the drink.

Constraints

• 1 \leq N \leq 100
• 1 \leq Q \lt P \leq 10^5
• 1 \leq D_i \leq 10^5
• All input values are integers.

Sample Input 1

3 100 50
60 20 40

Sample Output 1

70

If he uses the coupon and orders the second dish, he can get the drink by paying 50 yen for it and 20 yen for the dish, for a total of 70 yen, which is the minimum total payment needed.

Sample Input 2

3 100 50
60000 20000 40000

Sample Output 2

100

The total payment will be minimized by not using the coupon and paying the regular price of 100 yen.

Problem Statement

There are N balls.

The color of the i-th ball is C_i, and its size is S_i. Here, the colors are represented by integers 1, 2, \ldots, M.

For k = 1, 2, \ldots, M, output the maximum size of a ball of color k, or -1 if there is no ball of color k.

Constraints

• 1 \leq N, M \leq 100
• 1 \leq C_i \leq M
• 1 \leq S_i \leq 100
• All input values are integers.

Sample Input 1

4 5
1 3
2 10
1 7
4 9

Sample Output 1

7 10 -1 9 -1

The maximum size of a ball of color 1 is 7, that of a ball of color 2 is 10, and that of a ball of color 4 is 9.

There is no ball of color 3 or color 5.

Sample Input 2

5 5
2 6
5 12
5 2
5 9
2 7

Sample Output 2

-1 7 -1 -1 12

Problem Statement

We have a circular pizza.
Takahashi will cut this pizza using a sequence A of length N, according to the following procedure.

• First, make a cut from the center in the 12 o'clock direction.
• Next, do N operations. The i-th operation is as follows.
  • Rotate the pizza A_i degrees clockwise.
  • Then, make a cut from the center in the 12 o'clock direction.

For example, if A=(90,180,45,195), the procedure cuts the pizza as follows.

Find the center angle of the largest pizza after the procedure.

Constraints

• All values in input are integers.
• 1 \le N \le 359
• 1 \le A_i \le 359
• There will be no multiple cuts at the same position.

Sample Input 1

4
90 180 45 195

Sample Output 1

120

This input coincides with the example in the Problem Statement.
The center angle of the largest pizza is 120 degrees.

Sample Input 2

1
1

Sample Output 2

359

Sample Input 3

10
215 137 320 339 341 41 44 18 241 149

Sample Output 3

170

Problem Statement

A positive integer x is called a 321-like Number when it satisfies the following condition. This definition is the same as the one in Problem A.

• The digits of x are strictly decreasing from top to bottom.
• In other words, if x has d digits, it satisfies the following for every integer i such that 1 \le i < d:
  • (the i-th digit from the top of x) > (the (i+1)-th digit from the top of x).

Note that all one-digit positive integers are 321-like Numbers.

For example, 321, 96410, and 1 are 321-like Numbers, but 123, 2109, and 86411 are not.

Find the K-th smallest 321-like Number.

Constraints

• All input values are integers.
• 1 \le K
• At least K 321-like Numbers exist.

Sample Input 1

15

Sample Output 1

32

The 321-like Numbers are (1,2,3,4,5,6,7,8,9,10,20,21,30,31,32,40,\dots) from smallest to largest.
The 15-th smallest of them is 32.

Sample Input 2

321

Sample Output 2

9610

Sample Input 3

777

Sample Output 3

983210

Problem Statement

You are given a string S = S_1S_2\ldots S_N of length N consisting of lowercase English letters.

Additionally, you are given Q queries about the string S. For i = 1, 2, \ldots, Q, the i-th query is represented by two integers l_i, r_i and asks the following.

In the substring S_{l_i}S_{l_i+1}\ldots S_{r_i} of S, which ranges from the l_i-th to the r_i-th character, how many places are there where the same lowercase English letter occurs twice in a row? In other words, how many integers p satisfy l_i \leq p \leq r_i-1 and S_p = S_{p+1}?

Print the answer for each of the Q queries.

Constraints

• N and Q are integers.
• 1 \leq N, Q \leq 3 \times 10^5
• S is a string of length N consisting of lowercase English letters.
• l_i and r_i are integers.
• 1 \leq l_i \leq r_i \leq N

Sample Input 1

11 4
mississippi
3 9
4 10
4 6
7 7

Sample Output 1

2
2
0
0

The answers to the four queries are as follows.

• For the first query, S_3S_4\ldots S_9 = ssissip has two places where the same lowercase English letter occurs twice in a row: S_3S_4 = ss and S_6S_7 = ss.
• For the second query, S_4S_5\ldots S_{10} = sissipp has two places where the same lowercase English letter occurs twice in a row: S_6S_7 = ss and S_9S_{10} = pp.
• For the third query, S_4S_5S_6 = sis has zero places where the same lowercase English letter occurs twice in a row.
• For the fourth query, S_7 = s has zero places where the same lowercase English letter occurs twice in a row.

Sample Input 2

5 1
aaaaa
1 5

Sample Output 2

4

S_1S_2\ldots S_5 = aaaaa has four places where the same lowercase English letter occurs twice in a row: S_1S_2 = aa, S_2S_3 = aa, S_3S_4 = aa, and S_4S_5 = aa.

Problem Statement

The weather for the upcoming N days is given as a string S.
If the i-th character of S is S, then the weather on day i is sunny; if it is R, then the weather on day i is rainy.
Also, your current happiness is 0.

You can perform the following operation any number of times, possibly zero:

• Choose an integer i with 1 \le i \le N.
• If the weather on day i is sunny, change it to rainy; if it is rainy, change it to sunny.
• However, if you change the weather on day i, your happiness decreases by X_i.

After performing the operations, your happiness increases based on the final weather according to the following condition:

• For each integer i with 1 \le i \le N-1, if the weather on day i after modification is rainy and the weather on day i+1 is sunny, your happiness increases by Y_i.

Find the maximum value of happiness achievable by performing operations.

T test cases are given; solve each.

Constraints

• 1 \le T \le 10^4
• N is an integer between 2 and 2 \times 10^5, inclusive.
• S is a string of length N consisting of S and R.
• X_i is an integer between 1 and 10^9, inclusive.
• Y_i is an integer between 1 and 10^9, inclusive.
• The sum of N in a single input is at most 2 \times 10^5.

Sample Input 1

5
6
SRRRSR
3 1 4 1 5 9
2 6 5 3 5
6
RSRSRS
10 10 10 10 10 10
1 1 1 1 1
2
RR
4 3
2
10
RSSRSSRSSR
75 49 79 37 16 9 38 49 69 54
23 100 73 63 66 23 51 65 67
20
SSSRSSSRRRRSSRSSRSSR
343191362 223147518 135066250 426658267 693515093 8023388 383375974 712283203 40447501 19870690 318452142 356265717 283999278 209219229 418603824 39363351 392058270 254796273 110117486 64951139
576697130 385986330 895027325 654885799 784214084 577658764 761714876 583039741 943991250 446493376 701505924 402891440 963636095 919408713 238125227 871191978 843843821 397910552 529447424

Sample Output 1

5
3
0
165
5201284760

This input contains five test cases.

For the first test case, for example, you can maximize happiness by performing the following operations:

• Change the weather on day 3 from rainy to sunny. Happiness decreases by X_3 = 4, and the weather on each day becomes sunny, rainy, sunny, rainy, sunny, rainy.
• As a result of this operation, since day 2 is rainy and day 3 is sunny, happiness increases by Y_2 = 6, and since day 4 is rainy and day 5 is sunny, happiness increases by Y_4 = 3.
• The total happiness is (-4) + 6 + 3 = 5, which is the achievable maximum.

For the second and third test cases, performing no operations may be optimal.

For the fifth test case, note that the answer may not fit in a 32-bit integer type.

Problem Statement

You are given a string S of length N consisting of o and x.
It is guaranteed that S contains at least K occurrences of o.
Takahashi played a certain game N times.
In the i-th game, he won if the i-th character of S is o, and lost if it is x.

Takahashi chooses a pair of integers l and r satisfying the following conditions.

• 1 \leq l \leq r \leq N
• He won at least K times in the games from the l-th through the r-th.

Find the maximum possible value of the win rate in the games from the l-th through the r-th.

Constraints

• 1 \leq K \leq N \leq 10^6
• N and K are integers.
• S is a string of length N consisting of o and x.
• S contains at least K occurrences of o.

Sample Input 1

10 4
oxooxoxxox

Sample Output 1

0.6666666666

Choosing (1,6) as (l,r) gives a win rate of \frac{2}{3}.
It is impossible to make the win rate larger than this while satisfying the conditions.

Sample Input 2

5 1
xxoxx

Sample Output 2

1

Sample Input 3

16 10
xxxoxooooxoxoooo

Sample Output 3

0.769230769230769

Problem Statement

There is an undirected graph G with N vertices numbered 1 through N and zero edges.

Q queries are given. In the i-th query, an edge connecting vertices u_i and v_i is added to graph G.

Immediately after processing each query, determine whether it is possible to color each vertex of G white or black so that the following condition is satisfied, and if possible, find the minimum possible number of vertices colored black.

• For every edge, the two endpoints have different colors.

Constraints

• 2 \le N \le 2 \times 10^5
• 1 \le Q \le 2 \times 10^5
• 1 \le u_i \lt v_i \le N
• (u_i, v_i) \ne (u_j, v_j) \ (i \ne j)
• All input values are integers.

Sample Input 1

4 4
1 2
2 3
3 4
1 3

Sample Output 1

1
1
2
-1

Immediately after processing queries 1, 2, 3, a valid coloring exists.

For example, immediately after processing the third query, vertices 1, 2, 3, 4 can be colored white, black, white, black, respectively. No valid coloring with fewer black vertices exists, so output 2.

Immediately after processing the fourth query, no valid coloring exists. Thus, output -1.

Sample Input 2

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

Sample Output 2

1
2
2
3
3
3
3
4
4
4