Problem Statement

We have a sequence of N numbers: A = (a_1, a_2, \dots, a_N).
Process the Q queries explained below.

• Query i: You are given a pair of integers (x_i, k_i). Let us look at the elements of A one by one from the beginning: a_1, a_2, \dots Which element will be the k_i-th occurrence of the number x_i?
  Print the index of that element, or -1 if there is no such element.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq a_i \leq 10^9 (1 \leq i \leq N)
• 0 \leq x_i \leq 10^9 (1 \leq i \leq Q)
• 1 \leq k_i \leq N (1 \leq i \leq Q)
• All values in input are integers.

Sample Input 1

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

Sample Output 1

1
2
5
-1
3
6
-1
-1

1 occurs in A at a_1, a_2, a_5. Thus, the answers to Query 1 through 4 are 1, 2, 5, -1 in this order.

Sample Input 2

3 2
0 1000000000 999999999
1000000000 1
123456789 1

Sample Output 2

2
-1

Problem Statement

There are N types of beans, one bean of each type. The i-th type of bean has a deliciousness of A_i and a color of C_i. The beans are mixed and can only be distinguished by color.

You will choose one color of beans and eat one bean of that color. By selecting the optimal color, maximize the minimum possible deliciousness of the bean you eat.

Constraints

• 1 \leq N \leq 2 \times 10^{5}
• 1 \leq A_i \leq 10^{9}
• 1 \leq C_i \leq 10^{9}
• All input values are integers.

Sample Input 1

4
100 1
20 5
30 5
40 1

Sample Output 1

40

Note that beans of the same color cannot be distinguished from each other.

You can choose color 1 or color 5.

• There are two types of beans of color 1, with deliciousness of 100 and 40. Thus, the minimum deliciousness when choosing color 1 is 40.
• There are two types of beans of color 5, with deliciousness of 20 and 30. Thus, the minimum deliciousness when choosing color 5 is 20.

To maximize the minimum deliciousness, you should choose color 1, so print the minimum deliciousness in that case: 40.

Sample Input 2

10
68 3
17 2
99 2
92 4
82 4
10 3
100 2
78 1
3 1
35 4

Sample Output 2

35

Problem Statement

Solve the following problem for T test cases.

Given are non-negative integers a and s. Is there a pair of non-negative integers (x,y) that satisfies both of the conditions below?

• x\ \text{AND}\ y=a
• x+y=s

Constraints

• 1 \leq T \leq 10^5
• 0 \leq a,s \lt 2^{60}
• All values in input are integers.

Sample Input 1

2
1 8
4 2

Sample Output 1

Yes
No

In the first test case, some pairs such as (x,y)=(3,5) satisfy the conditions.

In the second test case, no pair of non-negative integers satisfies the conditions.

Sample Input 2

4
201408139683277485 381410962404666524
360288799186493714 788806911317182736
18999951915747344 451273909320288229
962424162689761932 1097438793187620758

Sample Output 2

No
Yes
Yes
No

Problem Statement

A "Snowflake Tree" is defined as a tree that can be generated by the following procedure:

1. Choose positive integers x,y.
2. Prepare one vertex.
3. Prepare x more vertices, and connect each of them to the vertex prepared in step 2.
4. For each of the x vertices prepared in step 3, attach y leaves to it.

The figure below shows a Snowflake Tree with x=4,y=2. The vertices prepared in steps 2, 3, 4 are shown in red, blue, and green, respectively.

You are given a tree T with N vertices. The vertices are numbered 1 to N, and the i-th edge (i=1,2,\dots,N-1) connects vertices u_i and v_i.

Consider deleting zero or more vertices of T and the edges adjacent to them so that the remaining graph becomes a single Snowflake Tree. Find the minimum number of vertices that must be deleted. Under the constraints of this problem, it is always possible to transform T into a Snowflake Tree.

Constraints

• 3 \leq N \leq 3 \times 10^5
• 1 \leq u_i < v_i \leq N
• The given graph is a tree.
• All input values are integers.

Sample Input 1

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

Sample Output 1

1

By deleting vertex 8, the given tree can be transformed into a Snowflake Tree with x=2,y=2.

Sample Input 2

3
1 2
2 3

Sample Output 2

0

The given tree is already a Snowflake Tree with x=1,y=1.

Sample Input 3

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

Sample Output 3

3

Problem Statement

A monster with health H has appeared in front of you, and a turn-based battle has started.

In each turn 1,2,…, you cast one of N spells, spells 1,…,N.

If you cast spell i in turn j, the monster's health reduces by d_i in each turn j,j+1,…,j+t_i －1.

Find the earliest turn that you can make the monster's health 0 or less.

Constraints

• 1 \leq N \leq 3 \times 10^5
• 1 \leq H \leq 10^{18}
• 1 \leq t_i,d_i \leq 10^9
• All values in the input are integers.

Sample Input 1

2 20
2 2
5 1

Sample Output 1

6

The following procedure makes the monster's health 0 or less in turn 6, which is the earliest.

• Cast spell 1 in turn 1. Due to the spell cast in turn 1, the monster's health reduces by 2 and becomes 18.
• Cast spell 2 in turn 2. Due to the spells cast in turns 1 and 2, the monster's health reduces by 2+1=3 and becomes 15.
• Cast spell 1 in turn 3. Due to the spells cast in turns 2 and 3, the monster's health reduces by 1+2=3 and becomes 12.
• Cast spell 2 in turn 4. Due to the spells cast in turns 2,3 and 4, the monster's health reduces by 1+2+1=4 and becomes 8.
• Cast spell 1 in turn 5. Due to the spells cast in turns 2,4 and 5, the monster's health reduces by 1+1+2=4 and becomes 4.
• Cast spell 2 in turn 6. Due to the spells cast in turns 2,4,5 and 6, the monster's health reduces by 1+1+2+1=5 and becomes -1.

Sample Input 2

10 200
1 21
1 1
1 1
8 4
30 1
3 1
10 2
8 1
9 1
4 4

Sample Output 2

9