Problem Statement

Takahashi has come to an amusement arcade with N yen (Japanese currency) in his pocket. In the arcade, he can pay X yen for Y tokens any number of times (possibly zero). Find the maximum total number of tokens that he can get.

Constraints

• 1 \leq N \leq 10^{12}
• 1 \leq X, Y \leq 10^{6}
• N, X, and Y are integers.

Sample Input 1

12 5 3

Sample Output 1

6

Initially, Takahashi has 12 yen.

• If he pays 5 yen for 3 tokens, he will have 7 yen and 3 tokens.
• If he again pays 5 yen for 3 tokens, he will have 2 yen and 6 tokens.

In this way, he can get 6 tokens in total, and there is no way to get more tokens. Thus, 6 should be printed.

Sample Input 2

4 5 3

Sample Output 2

0

Since he has less than 5 yen, he cannot buy any tokens.

Problem Statement

You are given integers A and C, and non-negative integers B and D. If \frac{A}{B}<\frac{C}{D}, print <; if \frac{A}{B}>\frac{C}{D}, print >; if \frac{A}{B}=\frac{C}{D}, print =.

Constraints

• -100 \leq A,B,C,D \leq 100
• B,D\neq 0
• A, B, C, and D are integers.

Sample Input 1

1 2 1 3

Sample Output 1

>

We have \frac{1}{2}>\frac{1}{3}, so you should print >.

Sample Input 2

-3 -6 1 2

Sample Output 2

=

We have \frac{-3}{-6}=\frac{1}{2}, so you should print =. Note that the given fractions may be reducible, and the given integers may be negative.

Sample Input 3

-1 3 1 -4

Sample Output 3

<

We have \frac{-1}{3}<\frac{1}{-4}, so you should print <.

Problem Statement

You are given an integer sequence of length N: A = (A_1, \dots, A_N).

Find the number of integers X that satisfy the following condition.

• There are integers i, j, and k such that A_i \times A_j \times A_k = X and 1 \leq i \lt j \lt k \leq N.

Constraints

• 3 \leq N \leq 100
• 1 \leq A_i \leq 100 \, (1 \leq i \leq N)
• All values in the input are integers.

Sample Input 1

4
2 1 3 2

Sample Output 1

3

X = 4, 6, and 12 satisfy the condition.

Sample Input 2

10
3 1 4 1 5 9 2 6 5 3

Sample Output 2

37

Problem Statement

N players will play a game using cards.

Initially, the first pile contains M cards, the second pile contains 0 cards, and each player has 0 cards.
Each card has one of the symbols +, 0, and - written on it. The symbol on the i-th card from the top of the initial first pile is S_i.

In the game, the players take turns doing the following, in this order: player 1, player 2, \ldots, player N-1, player N, player 1, player 2, \dots

• If the first pile contains 0 cards, end the game. Otherwise, the current player draws the top card from the first pile, and adds it to the player's hand. Then, according to the symbol written on that card, the player does the following.
  • If + is written, add all cards in the second pile to the player's hand.
  • If 0 is written, do nohing.
  • If - is written, move all cards in the player's hand to the second pile.

Find the number of cards in each player's hand at the end of the game.

Constraints

• 2 \leq N \leq 2\times 10^5
• 1 \leq M \leq 2\times 10^5
• S_i is +, 0, or -.

Sample Input 1

3 6
000--+

Sample Output 1

0
0
6

The game proceeds as follows.

• Player 1 draws a 0 card and adds it to the hand. Now, player 1 has 1 card.
• Player 2 draws a 0 card and adds it to the hand. Now, player 2 has 1 card.
• Player 3 draws a 0 card and adds it to the hand. Now, player 3 has 1 card.
• Player 1 draws a - card, adds it to the hand, and then moves all cards in the hand to the second pile. Now, player 1 has 0 cards, and the second pile has 2 cards.
• Player 2 draws a - card, adds it to the hand, and then moves all cards in the hand to the second pile. Now, player 2 has 0 cards, and the second pile has 4 cards.
• Player 3 draws a + card, adds it to the hand, and then adds all cards in the second pile to the hand. Now, player 3 has 6 cards, and the second pile has 0 cards.
• The first pile has no cards, so the game ends.

Sample Input 2

2 6
++++++

Sample Output 2

3
3

Sample Input 3

7 20
++-0+-0++-++0-+0-0-0

Sample Output 3

6
3
0
4
0
2
0

Problem Statement

A string consisting of ( and ) is said to be a correct bracket sequence if it can be made empty by erasing a contiguous occurrence of () zero or more times.

• For instance, (), (()), and (()())() are correct bracket sequences, while )(, ()), and (()()))(() are not.

You are given a string S consisting of ( and ). Determine whether S is a correct bracket sequence.

Constraints

• S is a non-empty string of length at most 2 \times 10^5 consisting of ( and ).

Sample Input 1

(())

Sample Output 1

Yes

One can make S empty by removing consecutive occurrences of () as follows, so S is a correct bracket sequence.

• Remove the second and third characters of the current string, making it ().
• Remove the first and second characters of the current string, making it empty.

Sample Input 2

())(

Sample Output 2

No

Sample Input 3

(

Sample Output 3

No

Sample Input 4

((())()()())()()

Sample Output 4

Yes

Problem Statement

Snuke played N matches of a 4-player game, and ranked 1-st A times, 2-nd B times, 3-rd C times, and 4-th D times.

Snuke is happy if the value of his average rank is at most X. At least how many additional matches must be played to make him happy?

Constraints

• 1\leq N \leq 10^{12}
• 0\leq A,B,C,D \leq 10^{12}
• A+B+C+D=N
• 1< X\leq 4
• N, A, B, C, and D are given as integers.
• X is given with three decimal places.

Sample Input 1

4
1 1 1 1
1.600

Sample Output 1

6

Now, the value of his average rank is 2.5. If six more matches are played and he ranks 1-st in all of them, his average rank will be 1.6, which is not greater than X=1.600.

Sample Input 2

10
0 0 0 10
4.000

Sample Output 2

0

The value of his average rank is already not greater than X=4.000, so no more matches need to be played.

Problem Statement

You are given an integer sequence of length N: A = (A_1, A_2, \ldots, A_N).

Print the maximum possible value of A_l + A_{l+1} + \cdots + A_r for a pair (l, r) such that 1 \leq l \leq r \leq N.

Constraints

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

Sample Input 1

10
-6 5 -3 3 -1 4 -1 5 -9 2

Sample Output 1

12

For (l, r) = (2, 8), we have A_2 + A_3 + \cdots + A_8 = 5 + (-3) + 3 + (-1) + 4 + (-1) + 5 = 12, which is the maximum possible value.

Sample Input 2

3
-1 -2 -3

Sample Output 2

-1

Sample Input 3

20
-14 74 -48 38 -51 43 5 37 -39 -29 80 -44 -55 59 17 89 -37 -68 38 -16

Sample Output 3

176

Problem Statement

You are given a positive integer N that has D digits when written in base 10.

For 1\leq k\leq D, let A_k be the k-th digit from the top when N is written in base 10.
Find the value \displaystyle\sum_{i=1}^{D-1}\sum_{j=i+1}^D \lvert A_i-A_j \rvert.

Constraints

• 2 \leq D \leq 2\times 10^5
• D is an integer.
• N is a D-digit positive integer.
• The topmost digit of N is not 0.

Sample Input 1

3
287

Sample Output 1

12

We have D=3, A_1=2, A_2=8, and A_3=7, so the sought value is \lvert 2-8 \rvert+\lvert 2-7 \rvert+\lvert 8-7 \rvert=12.

Sample Input 2

2
11

Sample Output 2

0

Sample Input 3

20
12345678901234567890

Sample Output 3

660

Problem Statement

There are N people numbered 1 to N.

You are given N pieces of information, each in this form: person A_i is taller than person B_i. Determine whether they are consistent.

Constraints

• 2 \leq N \leq 100
• 0 \leq M \leq 100
• 1 \leq A_i,B_i \leq N
• A_i \neq B_i
• All values in the input are integers.

Sample Input 1

3 3
1 2
2 3
3 1

Sample Output 1

No

It does not hold simultaneously that person 1 is taller than person 2, person 2 is taller than person 3, and person 3 is taller than person 1.

Sample Input 2

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

Sample Output 2

Yes

The same piece of information may be given multiple times.

Sample Input 3

3 3
1 2
2 1
1 3

Sample Output 3

No

Sample Input 4

100 0

Sample Output 4

Yes

Problem Statement

You are given points S(x_{\mathrm{s}}, y_{\mathrm{s}}) and T(x_{\mathrm{t}}, y_{\mathrm{t}}) in the xy-plane. You are also given N four-tuples (P_i, Q_i, R_i, W_i)(1 \leq i \leq N).

Consider the following procedure.

• First, choose an arbitrary (directed) curve C from point S(x_{\mathrm{s}}, y_{\mathrm{s}}) to T(x_{\mathrm{t}}, y_{\mathrm{t}})
• Next, choose arbitrary K distinct integers A_1, A_2, \ldots, A_K between 1 and N.
• Then, for each i = 1, 2, \ldots, K, do the following:
  • If the curve C has one or more common points with the line P_{A_i} x + Q_{A_i} y = R_{A_i}, you pay W_{A_i} yen (the currency in Japan).

Print the minimum possible amount of money you pay in total in the procedure above.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq N
• -10^9 \leq x_{\mathrm{s}}, y_{\mathrm{s}}, x_{\mathrm{t}}, y_{\mathrm{t}} \leq 10^9
• -10^9 \leq P_i, Q_i, R_i \leq 10^9
• 1 \leq W_i \leq 10^9
• P_i \neq 0 or Q_i \neq 0.
• For all i = 1, 2, \ldots, N, neither point S nor point T is on the line P_i x + Q_i y = R_i.
• All values in the input are integers.

Sample Input 1

4 3
-2 0 2 0
2 1 2 7
0 1 10 10
1 0 -1 3
-1 1 0 5

Sample Output 1

8

Consider the case where you choose a path along the x-axis from point S(-2, 0) to T(2, 0) as the curve C, and integers 2, 3, 4 as the 3 distinct integers between 1 and 4. Then,

• The curve C does not have a common point with the line P_2 x + Q_2 y = R_2 (i.e. the line y = 10).
• The curve C has a common point (-1, 0) with the line P_3 x + Q_3 y = R_3 (i.e. the line x = -1), so you pay W_3 = 3 yen.
• The curve C has a common point (0, 0) with the line P_4 x + Q_4 y = R_4 (i.e. the line -x + y = 0), so you pay W_4 = 5 yen.

Therefore, you pay 8 yen in total, which is the minimum possible amount.

Sample Input 2

2 2
0 0 0 0
1 2 3 4
2 4 6 8

Sample Output 2

0

Point S and point T may be the same point. Also, lines P_i x + Q_i y = R_i may be identical for multiple different i's.

Sample Input 3

20 17
-6 -77 40 99
-14 74 -48 27
-51 43 5 89
-39 -29 80 75
-55 59 17 39
-37 -68 38 62
14 31 43 49
49 -7 -65 13
-40 -45 36 32
-54 -43 99 77
-94 57 -22 12
-85 67 -46 72
95 68 55 67
-56 51 -38 22
32 -19 65 46
76 66 -53 8
35 -78 -41 30
-51 -85 24 64
45 -53 82 12
39 19 -52 86
-11 -67 -33 100

Sample Output 3

694

Problem Statement

Takahashi wants an integer, so he goes to an integer shop.

The integer shop sells every integer between 1 and 10^9, inclusive. The integer n is sold for A \times n + B \times d(n) yen (the currency in Japan), where d(n) denotes the sum of digits in the decimal notation of n.

Takahashi has X yen. Find the maximum integer he can buy.

Constraints

• 1 \leq A, B \leq 10^9
• A + B \leq X \leq 10^{18}
• All values in the input are integers.

Sample Input 1

3 4 50

Sample Output 1

12

Since the integer 12 is sold for A \times 12 + B \times 3 = 48 yen and 48 \leq X = 50, he can buy it.

We can show that the price of any integer greater than or equal to 13 is greater than X, so the maximum integer he can buy is 12.

Sample Input 2

199 211 10000000000

Sample Output 2

50251233

Problem Statement

You are given N segments [L_1, R_1], [L_2, R_2], \ldots, [L_N, R_N] on a number line.

A subset S of the set \lbrace 1, 2, \ldots, N \rbrace is said to be a good set if:

• for all i, j \in S, at least one of the following two conditions is satisfied:
  • the segment [L_i, R_i] contains the segment [L_j, R_j];
  • the segment [L_j, R_j] contains the segment [L_i, R_i].

Here, a segment [L, R] is said to contain another segment [L', R'] if and only if L \leq L' and R' \leq R.

Find the maximum possible size of a good set.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq L_i < R_i \leq 10^9
• All values in the input are integers.

Sample Input 1

4
1 3
2 4
3 4
1 4

Sample Output 1

3

The set \lbrace 2, 3, 4 \rbrace is a good set with the maximum size. Actually,

• for 2, 3 \in S, [L_2, R_2] contains [L_3, R_3];
• for 2, 4 \in S, [L_4, R_4] contains [L_2, R_2]; and
• for 3, 4 \in S, [L_4, R_4] contains [L_3, R_3];

so the size 3 should be printed.

Sample Input 2

3
0 1
0 1
0 1

Sample Output 2

3

Sample Input 3

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

Sample Output 3

4

Problem Statement

There is a tree with N vertices, whose vertices are numbered 1, \dots, N and edges are numbered 1, \dots, N-1. Edge i \, (1 \leq i \leq N - 1) connects vertices U_i and V_i.

Find the sum of the following value over all integer pairs (l, r) such that 1 \leq l \leq r \leq N - 1:

• the number of vertices that are reachable from vertex 1 using zero or more edges numbered between l and r, inclusive.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq U_i \lt V_i \leq N \, (1 \leq i \leq N - 1)
• The given graph is a tree.
• All values in the input are integers.

Sample Input 1

5
2 3
1 2
2 4
3 5

Sample Output 1

24

For example, if (l, r) = (2, 4), one can get from vertex 1 to vertices 1, 2, and 4; if (l, r) = (3, 3), one can get from vertex 1 to just vertex 1.

Sample Input 2

2
1 2

Sample Output 2

2

Sample Input 3

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

Sample Output 3

49

Problem Statement

For an integer sequence X = (X_1, X_2, \dots, X_k), let us define a function f(X) as follows:

• Let Y = (Y_1, Y_2, \dots, Y_k) be the sequence obtained by sorting X in ascending order.
• Then, \displaystyle f(X) = \sum_{i=1}^{k-1}(Y_{i+1}-Y_i)^2.

We have an integer sequence A = (A_1, A_2, \dots, A_N). Given Q queries in the following format, process them in order.

• Given integers l and r, find f(B), where B = (A_l, A_{l + 1}, \dots, A_r).

Constraints

• All values in the input are integers.
• 1≤N≤2\times10^4
• 1≤A_i≤10^9
• 1≤Q≤10^5
• For each query, 1≤l≤r≤N.

Sample Input 1

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

Sample Output 1

0
4
9
5

We have A = (3, 1, 4).

• In the 1-st query, f(B) = 0, because sorting B = (3) in ascending order yields (3).
• In the 2-nd query, f(B) = 4, because sorting B = (3, 1) in ascending order yields (1, 3).
• In the 3-rd query, f(B) = 9, because sorting B = (1, 4) in ascending order yields (1, 4).
• In the 4-th query, f(B) = 5, because sorting B = (3, 1, 4) in ascending order yields (1, 3, 4).

Sample Input 2

10
19 70 14 11 85 75 72 35 14 50
10
1 1
3 8
5 7
1 3
5 8
5 5
2 10
2 5
1 5
2 9

Sample Output 2

0
1928
109
2626
1478
0
1188
3370
2860
1788

Problem Statement

You are given an integer sequence A = (A_1, A_2, \ldots, A_N) of length N. Each element A_1, A_2, \ldots, A_N of A is a D-digit integer (without leading zeros) in the decimal notation, and none of its digits are 0.

You are given Q queries. Each query is of one of type 1, type 2, and type 3, which are described below. Process the given Q queries in the order given in the input.

[ Type 1 ]

1 x

Apply a left cyclic shift x times to the sequence A. In other words, if A = (a_1, a_2, \ldots, a_N), let A = (a_{x+1}, a_{x+2}, \ldots, a_N, a_1, a_2, \ldots, a_x).

[ Type 2 ]

2 l r y

Do the following for i = l, l+1, \ldots, r:

Let d_1 d_2 \ldots d_D be the decimal notation of A_i. Replace A_i with the integer d_{y+1} d_{y+2} \ldots d_D d_1 d_2 \ldots d_y, which is obtained by applying a left cyclic shift y times to the digits of A_i.

[ Type 3 ]

3 l r

Print A_l \oplus A_{l+1} \oplus \cdots \oplus A_r, where \oplus denotes the bitwise exclusive logical sum.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• 2 \leq D \leq 9
• 10^{D-1} \leq A_i < 10^D
• None of the digits of A_i is 0.
• 1 \leq x \leq N-1
• 1 \leq y \leq D-1
• 1 \leq l \leq r \leq N
• At least one of the given queries is of type 3.
• All values in the input are integers.

Sample Input 1

5 3
123 234 345 456 567
5
3 2 4
1 3
3 2 4
2 3 5 2
3 2 4

Sample Output 1

123
678
680

Initially, A = (A_1, A_2, A_3, A_4, A_5) = (123, 234, 345, 456, 567).

• For the 1-st query, print A_2 \oplus A_3 \oplus A_4 = 234 \oplus 345 \oplus 456 = 123.
• The 2-nd query makes A = (A_1, A_2, A_3, A_4, A_5) = (456, 567, 123, 234, 345).
• For the 3-rd query, print A_2 \oplus A_3 \oplus A_4 = 567 \oplus 123 \oplus 234 = 678.
• The 4-th query makes A = (A_1, A_2, A_3, A_4, A_5) = (456, 567, 312, 423, 534).
• For the 5-th query, print A_2 \oplus A_3 \oplus A_4 = 567 \oplus 312 \oplus 423 = 680.

Sample Input 2

20 6
318153 438943 474719 114997 373645 598458 427319 171794 653644 463294 123454 842368 264537 215892 467783 121159 836368 946718 889644 865849
20
2 6 9 3
2 8 13 5
2 1 6 3
2 14 20 5
1 7
2 14 15 4
3 8 8
2 4 5 3
2 7 17 2
1 19
2 13 16 4
2 4 9 2
3 11 14
1 8
2 2 17 3
3 6 9
3 6 16
2 16 17 2
1 1
3 3 20

Sample Output 2

346778
710529
89337
796525
709076