Problem Statement

A positive integer not less than 10 whose top digit (the most significant digit) in decimal representation is strictly larger than every other digit in that number is called a Snake number. For example, 31 and 201 are Snake numbers, but 35 and 202 are not.

Find how many Snake numbers exist between L and R, inclusive.

Constraints

• 10 \leq L \leq R \leq 10^{18}
• All input values are integers.

Sample Input 1

97 210

Sample Output 1

6

The Snake numbers between 97 and 210, inclusive, are 97, 98, 100, 200, 201, and 210: there are six.

Sample Input 2

1000 9999

Sample Output 2

2025

Sample Input 3

252509054433933519 760713016476190692

Sample Output 3

221852052834757

Problem Statement

There are N dominoes numbered from 1 to N. The size of domino i is S_i.
Consider arranging some dominoes in a line from left to right and then toppling them. When domino i falls to the right, if the size of the domino placed immediately to the right of domino i is at most 2 S_i, then that domino also falls to the right.

You decided to choose two or more dominoes and arrange them in a line from left to right. The arrangement of dominoes must satisfy the following conditions:

• The leftmost domino is domino 1.
• The rightmost domino is domino N.
• When only domino 1 is toppled to the right, domino N eventually falls to the right as well.

Does an arrangement of dominoes satisfying the conditions exist? If it exists, what is the minimum number of dominoes that need to be arranged?

You are given T test cases, solve the problem for each of them.

Constraints

• 1 \leq T \leq 10^5
• 2 \leq N \leq 2 \times 10^5
• 1 \leq S_i \leq 10^9
• The sum of N over all test cases is at most 2 \times 10^5.
• All input values are integers.

Sample Input 1

3
4
1 3 2 5
2
1 100
10
298077099 766294630 440423914 59187620 725560241 585990757 965580536 623321126 550925214 917827435

Sample Output 1

4
-1
3

For the 1st test case, arranging the dominoes from left to right in the order domino 1, domino 3, domino 2, domino 4 satisfies the conditions in the problem statement. Specifically, for the 3rd condition, when only domino 1 is toppled to the right, the dominoes fall in the following order:

• Domino 3 is placed to the right of domino 1. Since the size of domino 3, S_3 = 2, is not greater than S_1 \times 2 = 1 \times 2 = 2, domino 3 also falls to the right.
• Domino 2 is placed to the right of domino 3. Since the size of domino 2, S_2 = 3, is not greater than S_3 \times 2 = 2 \times 2 = 4, domino 2 also falls to the right.
• Domino 4 is placed to the right of domino 2. Since the size of domino 4, S_4 = 5, is not greater than S_2 \times 2 = 3 \times 2 = 6, domino 4 also falls to the right.

It is impossible to achieve the conditions in the problem statement by arranging 3 or fewer dominoes, so the answer is 4.

Problem Statement

You are given three positive integers N, M, and K. Here, N and M are different.
Print the K-th smallest positive integer divisible by exactly one of N and M.

Constraints

• 1 \leq N, M \leq 10^8
• 1 \leq K \leq 10^{10}
• N \neq M
• N, M, and K are integers.

Sample Input 1

2 3 5

Sample Output 1

9

The positive integers divisible by exactly one of 2 and 3 are 2, 3, 4, 8, 9, 10, \ldots in ascending order.
Note that 6 is not included because it is divisible by both 2 and 3.
The fifth smallest positive integer that satisfies the condition is 9, so we print 9.

Sample Input 2

1 2 3

Sample Output 2

5

The numbers that satisfy the condition are 1, 3, 5, 7, \ldots in ascending order.

Sample Input 3

100000000 99999999 10000000000

Sample Output 3

500000002500000000

Problem Statement

There are N people gathered for an event called Flowing Noodles. The people are lined up in a row, numbered 1 to N in order from front to back.

During the event, the following occurrence happens M times:

• At time T_i, a quantity W_i of noodles is flown down. The person at the front of the row gets all of it (if no one is in the row, no one gets it). That person then steps out of the row and returns to their original position in the row at time T_i+S_i.

A person who returns to the row at time X is considered to be in the row at time X.

After all the M occurrences, report the total amount of noodles each person has got.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq M \leq 2\times 10^5
• 0 <T_1 <\ldots < T_M \leq 10^9
• 1 \leq S_i \leq 10^9
• 1 \leq W_i \leq 10^9
• All input values are integers.

Sample Input 1

3 5
1 1 3
2 10 100
4 100 10000
10 1000 1000000000
100 1000000000 1

Sample Output 1

101
10
1000

The event proceeds as follows:

• At time 1, a quantity 1 of noodles is flown down. People 1, 2, and 3 are in the row, and the person at the front, person 1, gets the noodles and steps out of the row.
• At time 2, a quantity 10 of noodles is flown down. People 2 and 3 are in the row, and the person at the front, person 2, gets the noodles and steps out of the row.
• At time 4, person 1 returns to the row.
• At time 4, a quantity 100 of noodles is flown down. People 1 and 3 are in the row, and the person at the front, person 1, gets the noodles and steps out of the row.
• At time 10, a quantity 1000 of noodles is flown down. Only person 3 is in the row, and the person at the front, person 3, gets the noodles and steps out of the row.
• At time 100, a quantity 1000000000 of noodles is flown down. No one is in the row, so no one gets these noodles.
• At time 102, person 2 returns to the row.
• At time 10004, person 1 returns to the row.
• At time 1000000010, person 3 returns to the row.

The total amounts of noodles people 1, 2, and 3 have got are 101, 10, and 1000, respectively.

Sample Input 2

3 1
1 1 1

Sample Output 2

1
0
0

Sample Input 3

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

Sample Output 3

15

Problem Statement

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

Process Q queries in the order they are given. Each query is of one of the following two types:

• Type 1: Given in the form 1 p x. Change the value of A_p to x.
• Type 2: Given in the form 2 l r. print the number of occurrences of the second largest value in (A_l, A_{l+1}, \ldots, A_r). More precisely, print the number of integers i satisfying l \leq i \leq r such that there is exactly one distinct value greater than A_i among A_l, A_{l+1}, \ldots, A_r.

Constraints

• 1 \leq N, Q \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9
• For type-1 queries, 1 \leq p \leq N.
• For type-1 queries, 1 \leq x \leq 10^9.
• For type-2 queries, 1 \leq l \leq r \leq N.
• There is at least one type-2 query.
• All input values are integers.

Sample Input 1

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

Sample Output 1

1
0
2

Initially, A = (3, 3, 1, 4, 5).

For the first query, the second largest value in (3, 3, 1) is 1, which appears once in 3, 3, 1, so print 1.

For the second query, there is no second largest value in (5), so print 0.

The third query makes A = (3, 3, 3, 4, 5).

For the fourth query, the second largest value in (3, 3, 4), is 3, which appears twice in 3, 3, 4, so print 2.

Sample Input 2

1 1
1000000000
2 1 1

Sample Output 2

0

Sample Input 3

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

Sample Output 3

0
1
0
2
4