Problem Statement

The elder of Takahashi Village falls asleep immediately. Specifically, if S+0.5 seconds or more have passed since the elder was last tapped on the shoulder, the elder falls asleep.

Currently, the elder is awake, and an attendant has just tapped the elder on the shoulder.

From now on, the attendant will tap the elder's shoulder exactly N times. The i-th shoulder tap will be performed T_i seconds from now.

Determine whether the elder remains awake continuously from now until T_N seconds later.

Constraints

• 1 \leq N \leq 100
• 1 \leq S \leq 100
• 1 \leq T_i \leq 1000 (1 \leq i \leq N)
• T_i < T_{i+1} (1 \leq i \leq N-1)
• All input values are integers.

Sample Input 1

5 10
6 11 21 22 30

Sample Output 1

Yes

The attendant taps the shoulder in chronological order as follows:

• Taps after 6 seconds. At this time, only 6 seconds have passed since the elder was last tapped on the shoulder, so the elder is awake.
• Taps after 11 seconds. At this time, only 5 seconds have passed since the elder was last tapped on the shoulder, so the elder is awake.
• Taps after 21 seconds. At this time, only 10 seconds have passed since the elder was last tapped on the shoulder, so the elder is awake.
• Taps after 22 seconds. At this time, only 1 second has passed since the elder was last tapped on the shoulder, so the elder is awake.
• Taps after 30 seconds. At this time, only 8 seconds have passed since the elder was last tapped on the shoulder, so the elder is awake.

Since the elder is awake from now until 30 seconds later, output Yes.

Sample Input 2

2 100
1 200

Sample Output 2

No

The elder falls asleep 101.5 seconds from now. Therefore, output No.

Sample Input 3

10 22
47 81 82 95 117 146 165 209 212 215

Sample Output 3

No

Problem Statement

There is a bottle of disinfectant that can disinfect exactly M hands.

N aliens come one by one to disinfect their hands.
The i-th alien (1 \leq i \leq N) has H_i hands and wants to disinfect all of their hands once.

Determine how many aliens can disinfect all of their hands.
Here, even if there is not enough disinfectant left for an alien to disinfect all of their hands when they start, they will use up the remaining disinfectant.

Constraints

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

Sample Input 1

5 10
2 3 2 5 3

Sample Output 1

3

The aliens disinfect their hands in the following steps:

• The first alien disinfects their two hands. The remaining disinfectant can disinfect 10-2=8 hands.
• The second alien disinfects their three hands. The remaining disinfectant can disinfect 8-3=5 hands.
• The third alien disinfects their two hands. The remaining disinfectant can disinfect 5-2=3 hands.
• The fourth alien has five hands, but there is only enough disinfectant for three hands, so they use up the disinfectant without disinfecting all of their hands.

Thus, the first three aliens can disinfect all of their hands, so print 3.

Sample Input 2

5 10
2 3 2 3 5

Sample Output 2

4

Sample Input 3

1 5
1

Sample Output 3

1

All aliens can disinfect their hands.

Problem Statement

Given a non-negative integer X, perform the following operation for i=1,2,\dots,K in this order and find the resulting X.

• Round X off to the nearest 10^i.
  • Formally, replace X with Y that is "the largest multiple of 10^i that minimizes |Y-X|."
  • Here are some examples:
    • Rounding 273 off to the nearest 10^2 yields 300.
    • Rounding 999 off to the nearest 10^3 yields 1000.
    • Rounding 100 off to the nearest 10^{10} yields 0.
    • Rounding 1015 off to the nearest 10^1 yields 1020.

Constraints

• X and K are integers.
• 0 \le X < 10^{15}
• 1 \le K \le 15

Sample Input 1

2048 2

Sample Output 1

2100

X changes as 2048 \rightarrow 2050 \rightarrow 2100 by the operations.

Sample Input 2

1 15

Sample Output 2

0

Sample Input 3

999 3

Sample Output 3

1000

Sample Input 4

314159265358979 12

Sample Output 4

314000000000000

X may not fit into a 32-bit integer type.

Problem Statement

You are given a string S. Find the lexicographically smallest string S' obtained by permuting the characters of S.

Here, for different two strings s = s_1 s_2 \ldots s_n and t = t_1 t_2 \ldots t_m, s \lt t holds lexicographically when one of the conditions below is satisfied.

• There is an integer i\ (1 \leq i \leq \min(n,m)) such that s_i \lt t_i and s_j=t_j for all integers j\ (1 \leq j \lt i).
• s_i = t_i for all integers i\ (1 \leq i \leq \min(n,m)), and n \lt m.

Constraints

• S is a string of length between 1 and 2 \times 10^5 (inclusive) consisting of lowercase English letters.

Sample Input 1

aba

Sample Output 1

aab

Three strings can be obtained by permuting aba:

• aba
• aab
• baa

The lexicographically smallest among them is aab.

Sample Input 2

zzzz

Sample Output 2

zzzz

Problem Statement

We have a multiset of integers S, which is initially empty.

Given Q queries, process them in order. Each query is of one of the following types.

• 1 x: Insert an x into S.

• 2 x c: Remove an x from S m times, where m = \mathrm{min}(c,( the number of x's contained in S)).

• 3 : Print ( maximum value of S)-( minimum value of S). It is guaranteed that S is not empty when this query is given.

Constraints

• 1 \leq Q \leq 2\times 10^5
• 0 \leq x \leq 10^9
• 1 \leq c \leq Q
• When a query of type 3 is given, S is not empty.
• All values in input are integers.

Sample Input 1

8
1 3
1 2
3
1 2
1 7
3
2 2 3
3

Sample Output 1

1
5
4

The multiset S transitions as follows.

• 1-st query: insert 3 into S. S is now \lbrace 3 \rbrace.
• 2-nd query: insert 2 into S. S is now \lbrace 2, 3 \rbrace.
• 3-rd query: the maximum value of S = \lbrace 2, 3\rbrace is 3 and its minimum value is 2, so print 3-2=1.
• 4-th query: insert 2 into S. S is now \lbrace 2,2,3 \rbrace.
• 5-th query: insert 7 into S. S is now \lbrace 2, 2,3, 7\rbrace.
• 6-th query: the maximum value of S = \lbrace 2,2,3, 7\rbrace is 7 and its minimum value is 2, so print 7-2=5.
• 7-th query: since there are two 2's in S and \mathrm{min(2,3)} = 2, remove 2 from S twice. S is now \lbrace 3, 7\rbrace.
• 8-th query: the maximum value of S = \lbrace 3, 7\rbrace is 7 and its minimum value is 3, so print 7-3=4.

Sample Input 2

4
1 10000
1 1000
2 100 3
1 10

Sample Output 2

If the given queries do not contain that of type 3, nothing should be printed.

Problem Statement

Takahashi has decided to fly in the sky with balloons. Takahashi is at altitude H at time 0 (the unit is seconds), and will fly for 10^9 seconds from now.

Takahashi can change his flying altitude by up to 1 per second. However, he cannot make his altitude 0 or less.

• In other words, if F(t) denotes Takahashi's altitude at time t, then F(t) satisfies all of the following conditions:
  • F(0) = H
  • -1 \leq \dfrac{F(u) - F(t)}{u - t} \leq 1 for 0 \leq t \lt u \leq 10^9.
  • F(t) \gt 0 for 0 \leq t \leq 10^9.

There are N goals regarding altitude. The i-th goal is to make the altitude at time t_i at least l_i and at most u_i.
Is it possible for Takahashi to fly in a way that achieves all goals?

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

Constraints

• 1 \leq T \leq 10^5
• 1 \leq N \leq 10^5
• 1 \leq H \leq 10^9
• 1 \leq t_1 \lt t_2 \lt \dots \lt t_N \leq 10^9
• 1 \leq l_i \leq u_i \leq 10^9
• The sum of N over all test cases is at most 10^5.
• All input values are integers.

Sample Input 1

3
2 5
3 1 4
8 9 11
2 6
1 1 4
3 5 8
10 36
27 37 38
30 34 54
38 20 77
45 1 36
49 38 51
52 31 58
65 43 60
71 14 42
73 36 38
85 14 29

Sample Output 1

Yes
No
Yes

For the first test case, Takahashi can achieve all goals by flying as follows:

• At time 0, he is at altitude 5.
• From time 0 to time 2, he descends at a rate of 0.5 per second.
• At time 2, he is at altitude 5 - 0.5 \times 2 = 4.
• From time 2 to time 3, he stays at the same altitude.
• At time 3, he is at altitude 4. He satisfies the first goal.
• From time 3 to time 8, he ascends at a rate of 1 per second.
• At time 8, he is at altitude 4 + 1 \times 5 = 9. He satisfies the second goal.

For the second test case, he cannot achieve all goals no matter how he flies.

Problem Statement

How many positive integers no greater than N can be represented as a^2 \times b \times c^2 with three primes a,b, and c such that a<b<c?

Constraints

• N is an integer satisfying 300 \le N \le 10^{12}.

Sample Input 1

1000

Sample Output 1

3

The conforming integers no greater than 1000 are the following three.

• 300 = 2^2 \times 3 \times 5^2
• 588 = 2^2 \times 3 \times 7^2
• 980 = 2^2 \times 5 \times 7^2

Sample Input 2

1000000000000

Sample Output 2

2817785

Problem Statement

You are given an undirected graph consisting of N vertices and M edges.
For i = 1, 2, \ldots, M, the i-th edge is an undirected edge connecting vertex u_i and v_i that is initially passable if a_i = 1 and initially impassable if a_i = 0. Additionally, there are switches on K of the vertices: vertex s_1, vertex s_2, \ldots, vertex s_K.

Takahashi is initially on vertex 1, and will repeat performing one of the two actions below, Move or Hit Switch, which he may choose each time, as many times as he wants.

• Move: Choose a vertex adjacent to the vertex he is currently on via an edge, and move to that vertex.
• Hit Switch: If there is a switch on the vertex he is currently on, hit it. This will invert the passability of every edge in the graph. That is, a passable edge will become impassable, and vice versa.

Determine whether Takahashi can reach vertex N, and if he can, print the minimum possible number of times he performs Move before reaching vertex N.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 0 \leq K \leq N
• 1 \leq u_i, v_i \leq N
• u_i \neq v_i
• a_i \in \lbrace 0, 1\rbrace
• 1 \leq s_1 \lt s_2 \lt \cdots \lt s_K \leq N
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

5

Takahashi can reach vertex N as follows.

• Move from vertex 1 to vertex 2.
• Move from vertex 2 to vertex 3.
• Hit the switch on vertex 3. This inverts the passability of every edge in the graph.
• Move from vertex 3 to vertex 1.
• Move from vertex 1 to vertex 4.
• Hit the switch on vertex 4. This again inverts the passability of every edge in the graph.
• Move from vertex 4 to vertex 5.

Here, Move is performed five times, which is the minimum possible number.

Sample Input 2

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

Sample Output 2

-1

The given graph may be disconnected or contain multi-edges. In this sample input, there is no way for Takahashi to reach vertex N, so you should print -1.

Problem Statement

You are given N linear functions f_1, f_2, \ldots, f_N, where f_i(x) = A_i x + B_i.

Find the maximum possible value of f_{p_1}(f_{p_2}(\ldots f_{p_K}(1) \ldots )) for a sequence p = (p_1, p_2, \ldots, p_K) of K distinct integers between 1 and N, inclusive.

Constraints

• 1 \leq N \leq 2 \times 10^{5}
• 1 \leq K \leq \text{min}(N,10)
• 1 \leq A_i, B_i \leq 50 (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

3 2
2 3
1 5
4 2

Sample Output 1

26

Here are all possible p and the corresponding values of f_{p_1}(f_{p_2}(1)):

• p= ( 1,2 ) : f_1(f_2(1))=15
• p= ( 1,3 ) : f_1(f_3(1))=15
• p= ( 2,1 ) : f_2(f_1(1))=10
• p= ( 2,3 ) : f_2(f_3(1))=11
• p= ( 3,1 ) : f_3(f_1(1))=22
• p= ( 3,2 ) : f_3(f_2(1))=26

Therefore, print 26.

Sample Input 2

10 3
48 40
34 22
24 37
45 40
48 31
49 44
45 40
44 6
35 22
39 28

Sample Output 2

216223