Problem Statement

Takahashi is making a computer baseball game.
He will write a program that shows a batter's batting average with a specified number of digits.

There are integers A and B, which satisfy 1 \leq A \leq 10 and 0 \leq B \leq A.
Let S be the string obtained as follows.

• Round off \dfrac{B}{A} to three decimal digits, then write the integer part (1 digit), . (the decimal point), and the decimal part (3 digits) in this order, with trailing zeros.

For example, if A=7 and B=4, then \dfrac{B}{A} = \dfrac{4}{7} = 0.571428\dots rounded off to three decimal digits is 0.571. Thus, S is 0.571.

You are given A and B as the input and asked to print S.

Constraints

• 1 \leq A \leq 10
• 0 \leq B \leq A
• A and B are integers.

Sample Input 1

7 4

Sample Output 1

0.571

As explained in the Problem Statement, \dfrac{B}{A} = \dfrac{4}{7} = 0.571428\dots rounded off to three decimal digits is 0.571. Thus, S is 0.571.

Sample Input 2

7 3

Sample Output 2

0.429

\dfrac{B}{A} = \dfrac{3}{7} = 0.428571\dots rounded off to three decimal digits is 0.429. (Note that it got rounded up.)
Thus, S is 0.429.

Sample Input 3

2 1

Sample Output 3

0.500

\dfrac{B}{A} = \dfrac{1}{2} = 0.5 rounded off to three decimal digits is again 0.5.
Thus, S is 0.500. Note that it must have three decimal places.

Sample Input 4

10 10

Sample Output 4

1.000

Sample Input 5

1 0

Sample Output 5

0.000

Problem Statement

You are given a 3-digit positive integer N. Determine whether all digits are the same when N is represented in decimal.

Constraints

• 100 \leq N \leq 999
• The input value is an integer.

Sample Input 1

444

Sample Output 1

Yes

The digits of 444 are 4,4,4, which are the same, so output Yes.

Sample Input 2

160

Sample Output 2

No

The digits of 160 are 1,6,0, which are not the same, so output No.

Sample Input 3

999

Sample Output 3

Yes

Problem Statement

N students took an exam. The students are labeled as Student 1, Student 2, \dots, Student N, and Student i scored a_i points.

A student who scored less than P points are considered to have failed the exam and cannot earn the credit. Find the number of students who failed the exam.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq P \leq 100
• 0 \leq a_i \leq 100 (1 \leq i \leq N)
• All values in input are integers.

Sample Input 1

4 50
80 60 40 0

Sample Output 1

2

Students 1 and 2, who scored 80 and 60 points, respectively, succeeded in scoring at least 50 points to earn the credit.
On the other hand, Students 3 and 4, who scored 40 and 0 points, respectively, fell below 50 points and failed the exam. Thus, the answer is 2.

Sample Input 2

3 90
89 89 89

Sample Output 2

3

Sample Input 3

2 22
6 37

Sample Output 3

1

Problem Statement

You have an empty sequence A. There are Q queries given, and you need to process them in the order they are given.
The queries are of the following two types:

• 1 x: Append x to the end of A.
• 2 k: Find the k-th value from the end of A. It is guaranteed that the length of A is at least k when this query is given.

Constraints

• 1 \leq Q \leq 100
• In the first type of query, x is an integer satisfying 1 \leq x \leq 10^9.
• In the second type of query, k is a positive integer not greater than the current length of sequence A.

Sample Input 1

5
1 20
1 30
2 1
1 40
2 3

Sample Output 1

30
20

• Initially, A is empty.
• The first query appends 20 to the end of A, making A=(20).
• The second query appends 30 to the end of A, making A=(20,30).
• The answer to the third query is 30, which is the 1-st value from the end of A=(20,30).
• The fourth query appends 40 to the end of A, making A=(20,30,40).
• The answer to the fifth query is 20, which is the 3-rd value from the end of A=(20,30,40).

Problem Statement

There are N dishes, and the i-th dish has a sweetness of A_i and a saltiness of B_i.

Takahashi plans to arrange these N dishes in any order he likes and eat them in that order.

He will eat the dishes in the arranged order, but he will stop eating as soon as the total sweetness of the dishes he has eaten exceeds X or the total saltiness exceeds Y.

Find the minimum possible number of dishes that he will end up eating.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq X, Y \leq 2 \times 10^{14}
• 1 \leq A_i, B_i \leq 10^9
• All input values are integers.

Sample Input 1

4 7 18
2 3 5 1
8 8 1 4

Sample Output 1

2

The i-th dish will be denoted as dish i.

If he arranges the four dishes in the order 2, 3, 1, 4, as soon as he eats dishes 2 and 3, their total sweetness is 8, which is greater than 7. Therefore, in this case, he will end up eating two dishes.

The number of dishes he will eat cannot be 1 or less, so print 2.

Sample Input 2

5 200000000000000 200000000000000
1 1 1 1 1
2 2 2 2 2

Sample Output 2

5

Sample Input 3

8 30 30
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1

Sample Output 3

6

Problem Statement

You are given a string S of length N. You are also given Q queries, which you should process in order.

The i-th query is as follows:

• Given an integer X_i and a character C_i, replace the X_i-th character of S with C_i. Then, print the number of times the string ABC appears as a substring in S.

Here, a substring of S is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of S.
For example, ab is a substring of abc, but ac is not a substring of abc.

Constraints

• 3 \le N \le 2 \times 10^5
• 1 \le Q \le 2 \times 10^5
• S is a string of length N consisting of uppercase English letters.
• 1 \le X_i \le N
• C_i is an uppercase English letter.

Sample Input 1

7 4
ABCDABC
4 B
3 A
5 C
4 G

Sample Output 1

2
1
1
0

After processing each query, S becomes as follows.

• After the first query: S= ABCBABC. In this string, ABC appears twice as a substring.
• After the second query: S= ABABABC. In this string, ABC appears once as a substring.
• After the third query: S= ABABCBC. In this string, ABC appears once as a substring.
• After the fourth query: S= ABAGCBC. In this string, ABC appears zero times as a substring.

Sample Input 2

3 3
ABC
1 A
2 B
3 C

Sample Output 2

1
1
1

There are cases where S does not change through processing a query.

Sample Input 3

15 10
BBCCBCACCBACACA
9 C
11 B
5 B
11 B
4 A
8 C
8 B
5 B
7 B
14 B

Sample Output 3

0
0
0
0
1
1
2
2
1
1

Problem Statement

There is one integer X written on a blackboard.

You are given Q queries to process in order. The i-th query (1 \le i \le Q) is as follows.

Two integers A_i and B_i are given. Write two new integers A_i and B_i on the blackboard.

Then, output the median of the 2i+1 integers written on the blackboard.

Constraints

• 1 \le X \le 10^9
• 1 \le Q \le 2 \times 10^5
• 1 \le A_i, B_i \le 10^9
• All input values are integers.

Sample Input 1

5
3
2 3
1 2
8 9

Sample Output 1

3
2
3

In the first query, the integers written on the blackboard become 5, 2, 3, and their median is 3.

In the second query, the integers written on the blackboard become 5, 2, 3, 1, 2, and their median is 2.

In the third query, the integers written on the blackboard become 5, 2, 3, 1, 2, 8, 9, and their median is 3.

Sample Input 2

1
4
2 3
4 5
6 7
8 9

Sample Output 2

2
3
4
5

Sample Input 3

278117031
7
167642909 517897721
148434323 567739597
319926999 481642530
659199879 252516557
49913403 798318034
89701408 892537201
199166668 742285869

Sample Output 3

278117031
278117031
319926999
319926999
319926999
319926999
319926999

Problem Statement

You are given a sequence A=(A_1,\ldots,A_N) of length N.

Find \displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^{N}\left\lfloor\frac{\max(A_i,A_j)}{\min(A_i,A_j)}\right\rfloor.

Here, \lfloor x \rfloor represents the greatest integer not greater than x. For example, \lfloor 3.14 \rfloor=3 and \lfloor 2 \rfloor=2.

Constraints

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

Sample Input 1

3
3 1 4

Sample Output 1

8

The sought value is

\left\lfloor\frac{\max(3,1)}{\min(3,1)}\right\rfloor + \left\lfloor\frac{\max(3,4)}{\min(3,4)}\right\rfloor + \left\lfloor\frac{\max(1,4)}{\min(1,4)}\right\rfloor\\ =\left\lfloor\frac{3}{1}\right\rfloor + \left\lfloor\frac{4}{3}\right\rfloor + \left\lfloor\frac{4}{1}\right\rfloor\\ =3+1+4\\ =8.

Sample Input 2

6
2 7 1 8 2 8

Sample Output 2

53

Sample Input 3

12
3 31 314 3141 31415 314159 2 27 271 2718 27182 271828

Sample Output 3

592622

Problem Statement

You are given a tree with N vertices.
The vertices are numbered vertex 1, vertex 2, \ldots, vertex N, and the i-th edge (1\leq i\leq N-1) connects vertices U_i and V_i.

Takahashi will color each vertex with one of colors 1, 2, \ldots, K.
Color i can be used to color at most C_i vertices.

Determine whether it is possible to color the vertices satisfying the following condition, and if so, output one valid coloring.

• For every edge, there exists some i (1\leq i\leq K) such that both of the two subtrees obtained by cutting the tree at that edge contain at least one vertex colored with color i.

You are given T test cases; solve each of them.

Constraints

• 1\leq T\leq 10^5
• 2\leq N\leq 3\times 10^5
• 1\leq K\leq N
• 1\leq U_i,V_i\leq N
• The given graph is a tree.
• 1\leq C_i\leq N
• C_1+C_2+\cdots+C_K\geq N
• All input values are integers.
• The sum of N over all test cases does not exceed 3\times 10^5.

Sample Input 1

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

Sample Output 1

3 2 2 1 1
-1

For the first test case, suppose the vertices are colored as in the sample output.
That is, vertex 1 is colored with color 3, vertex 2 with color 2, vertex 3 with color 2, vertex 4 with color 1, and vertex 5 with color 1.

If we cut the edge connecting vertices 1 and 2, the tree splits into the subtree consisting of vertices 1,3 and the subtree consisting of vertices 2,4,5; both subtrees contain a vertex colored with color 2 (vertex 3 or vertex 2, respectively).
Such a color exists no matter which edge of the given tree is cut, so the coloring in the sample output satisfies the condition.

For the second test case, there is no valid coloring satisfying the condition.