Problem Statement

Takahashi wants to send a letter to Santa Claus. He has an envelope with an X-yen (Japanese currency) stamp stuck on it.
To be delivered to Santa Claus, the envelope must have stamps in a total value of at least Y yen.
Takahashi will put some more 10-yen stamps so that the envelope will have stamps worth at least Y yen in total.
At least how many more 10-yen stamps does Takahashi need to put on the envelope?

Constraints

• X and Y are integers.
• 1 \le X,Y \le 1000

Sample Input 1

80 94

Sample Output 1

2

• After adding zero 10-yen stamps to the 80-yen stamp, the total is 80 yen, which is less than the required amount of 94 yen.
• After adding one 10-yen stamp to the 80-yen stamp, the total is 90 yen, which is less than the required amount of 94 yen.
• After adding two 10-yen stamps to the 80-yen stamp, the total is 100 yen, which is not less than the required amount of 94 yen.

Sample Input 2

1000 63

Sample Output 2

0

The envelope may already have a stamp with enough value.

Sample Input 3

270 750

Sample Output 3

48

Problem Statement

Given a string S, print AC if it perfectly matches Hello,World!; otherwise, print WA.

Constraints

• 1 \le |S| \le 15
• S consists of English lowercase letters, English uppercase letters, ,, and !.

Sample Input 1

Hello,World!

Sample Output 1

AC

The string S perfectly matches Hello,World!.

Sample Input 2

Hello,world!

Sample Output 2

WA

The seventh character from the beginning should be an uppercase W in Hello,World!, but S has a lowercase w in that position. Thus, S does not match Hello,World!.

Sample Input 3

Hello!World!

Sample Output 3

WA

Problem Statement

You are given a sequence of 26 integers P=(P_1,P_2, \ldots ,P_{26}) consisting of integers from 1 through 26. It is guaranteed that all elements in P are distinct.

Print a string S of length 26 that satisfies the following condition.

• For every i (1 \leq i \leq 26), the i-th character of S is the lowercase English letter that comes P_i-th in alphabetical order.

Constraints

• 1 \leq P_i \leq 26
• P_i \neq P_j (i \neq j)
• All values in input are integers.

Sample Input 1

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Sample Output 1

abcdefghijklmnopqrstuvwxyz

Sample Input 2

2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Sample Output 2

bacdefghijklmnopqrstuvwxyz

Sample Input 3

5 11 12 16 25 17 18 1 7 10 4 23 20 3 2 24 26 19 14 9 6 22 8 13 15 21

Sample Output 3

eklpyqragjdwtcbxzsnifvhmou

Problem Statement

A supermarket sells egg packs.

A pack of 6 eggs costs S yen, a pack of 8 eggs costs M yen, and a pack of 12 eggs costs L yen.

When you can buy any number of each pack, find the minimum amount of money required to purchase at least N eggs.

Constraints

• 1 \leq N \leq 100
• 1 \leq S,M,L \leq 10^4
• All input values are integers.

Sample Input 1

16 120 150 200

Sample Output 1

300

It is optimal to buy two 8-egg packs.

Sample Input 2

10 100 50 10

Sample Output 2

10

It is optimal to buy one 12-egg pack.

Sample Input 3

99 600 800 1200

Sample Output 3

10000

It is optimal to buy five 8-egg packs and five 12-egg packs.

Problem Statement

On a two-dimensional plane, Takahashi is initially at point (0, 0), and his initial health is H. M items to recover health are placed on the plane; the i-th of them is placed at (x_i,y_i).

Takahashi will make N moves. The i-th move is as follows.

1. Let (x,y) be his current coordinates. He consumes a health of 1 to move to the following point, depending on S_i, the i-th character of S:

   • (x+1,y) if S_i is R;
   • (x-1,y) if S_i is L;
   • (x,y+1) if S_i is U;
   • (x,y-1) if S_i is D.

2. If Takahashi's health has become negative, he collapses and stops moving. Otherwise, if an item is placed at the point he has moved to, and his health is strictly less than K, then he consumes the item there to make his health K.

Determine if Takahashi can complete the N moves without being stunned.

Constraints

• 1\leq N,M,H,K\leq 2\times 10^5
• S is a string of length N consisting of R, L, U, and D.
• |x_i|,|y_i| \leq 2\times 10^5
• (x_i, y_i) are pairwise distinct.
• All values in the input are integers, except for S.

Sample Input 1

4 2 3 1
RUDL
-1 -1
1 0

Sample Output 1

Yes

Initially, Takahashi's health is 3. We describe the moves below.

• 1-st move: S_i is R, so he moves to point (1,0). His health reduces to 2. Although an item is placed at point (1,0), he do not consume it because his health is no less than K=1.

• 2-nd move: S_i is U, so he moves to point (1,1). His health reduces to 1.

• 3-rd move: S_i is D, so he moves to point (1,0). His health reduces to 0. An item is placed at point (1,0), and his health is less than K=1, so he consumes the item to make his health 1.

• 4-th move: S_i is L, so he moves to point (0,0). His health reduces to 0.

Thus, he can make the 4 moves without collapsing, so Yes should be printed. Note that the health may reach 0.

Sample Input 2

5 2 1 5
LDRLD
0 0
-1 -1

Sample Output 2

No

Initially, Takahashi's health is 1. We describe the moves below.

• 1-st move: S_i is L, so he moves to point (-1,0). His health reduces to 0.

• 2-nd move: S_i is D, so he moves to point (-1,-1). His health reduces to -1. Now that the health is -1, he collapses and stops moving.

Thus, he will be stunned, so No should be printed.

Note that although there is an item at his initial point (0,0), he does not consume it before the 1-st move, because items are only consumed after a move.

Problem Statement

There are N people numbered 1, 2, \ldots, N on a two-dimensional plane, and person i is at the point represented by the coordinates (X_i,Y_i).

Person 1 has been infected with a virus. The virus spreads to people within a distance of D from an infected person.

Here, the distance is defined as the Euclidean distance, that is, for two points (a_1, a_2) and (b_1, b_2), the distance between these two points is \sqrt {(a_1-b_1)^2 + (a_2-b_2)^2}.

After a sufficient amount of time has passed, that is, when all people within a distance of D from person i are infected with the virus if person i is infected, determine whether person i is infected with the virus for each i.

Constraints

• 1 \leq N, D \leq 2000
• -1000 \leq X_i, Y_i \leq 1000
• (X_i, Y_i) \neq (X_j, Y_j) if i \neq j.
• All input values are integers.

Sample Input 1

4 5
2 -1
3 1
8 8
0 5

Sample Output 1

Yes
Yes
No
Yes

The distance between person 1 and person 2 is \sqrt 5, so person 2 gets infected with the virus.
Also, the distance between person 2 and person 4 is 5, so person 4 gets infected with the virus.
Person 3 has no one within a distance of 5, so they will not be infected with the virus.

Sample Input 2

3 1
0 0
-1000 -1000
1000 1000

Sample Output 2

Yes
No
No

Sample Input 3

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

Sample Output 3

Yes
No
No
Yes
Yes
Yes
Yes
Yes
No

Problem Statement

You are given a positive integer N. It is known that N can be represented as N=p^2q using two different prime numbers p and q.

Find p and q.

You have T test cases to solve.

Constraints

• All values in the input are integers.
• 1\leq T\leq 10
• 1\leq N \leq 9\times 10^{18}
• N can be represented as N=p^2q using two different prime numbers p and q.

Sample Input 1

3
2023
63
1059872604593911

Sample Output 1

17 7
3 7
104149 97711

For the first test case, we have N=2023=17^2\times 7. Thus, p=17 and q=7.

Problem Statement

The Kingdom of AtCoder has N cities called City 1,2,\ldots,N and M roads called Road 1,2,\ldots,M.
Road i connects Cities A_i and B_i bidirectionally and has a length of C_i.
One can travel between any two cities using some roads.

Under financial difficulties, the kingdom has decided to maintain only N-1 roads so that one can still travel between any two cities using those roads and abandon the rest.

Let d_i be the total length of the roads one must use when going from City 1 to City i using only maintained roads. Print a choice of roads to maintain that minimizes d_2+d_3+\ldots+d_N.

Constraints

• 2 \leq N \leq 2\times 10^5
• N-1 \leq M \leq 2\times 10^5
• 1 \leq A_i < B_i \leq N
• (A_i,B_i)\neq(A_j,B_j) if i\neq j.
• 1\leq C_i \leq 10^9
• One can travel between any two cities using some roads.
• All values in input are integers.

Sample Input 1

3 3
1 2 1
2 3 2
1 3 10

Sample Output 1

1 2

Here are the possible choices of roads to maintain and the corresponding values of d_i.

• Maintain Road 1 and 2: d_2=1, d_3=3.
• Maintain Road 1 and 3: d_2=1, d_3=10.
• Maintain Road 2 and 3: d_2=12, d_3=10.

Thus, maintaining Road 1 and 2 minimizes d_2+d_3.

Sample Input 2

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

Sample Output 2

3 1 2

Problem Statement

For two sets of integers, A and B, such that A \cap B = \emptyset, we define f(A,B) as follows.

• Let C=(C_1,C_2,\dots,C_{|A|+|B|}) be a sequence consisting of the elements of A \cup B, sorted in ascending order.
• Take k_1,k_2,\dots,k_{|A|} such that A=\lbrace C_{k_1},C_{k_2},\dots,C_{k_{|A|}}\rbrace. Then, let \displaystyle f(A,B)=\sum_{i=1}^{|A|} k_i.

For example, if A=\lbrace 1,3\rbrace and B=\lbrace 2,8\rbrace, then C=(1,2,3,8), so A=\lbrace C_1,C_3\rbrace; thus, f(A,B)=1+3=4.

We have N sets of integers, S_1,S_2\dots,S_N, each of which has M elements. For each i\ (1 \leq i \leq N), S_i = \lbrace A_{i,1},A_{i,2},\dots,A_{i,M}\rbrace. Here, it is guaranteed that S_i \cap S_j = \emptyset\ (i \neq j).

Find \displaystyle \sum_{1\leq i<j \leq N} f(S_i, S_j).

Constraints

• 1\leq N \leq 10^4
• 1\leq M \leq 10^2
• 1\leq A_{i,j} \leq 10^9
• If i_1 \neq i_2 or j_1 \neq j_2, then A_{i_1,j_1} \neq A_{i_2,j_2}.
• All input values are integers.

Sample Input 1

3 2
1 3
2 8
4 6

Sample Output 1

12

S_1 and S_2 respectively coincide with A and B exemplified in the problem statement, and f(S_1,S_2)=1+3=4. Since f(S_1,S_3)=1+2=3 and f(S_2,S_3)=1+4=5, the answer is 4+3+5=12.

Sample Input 2

1 1
306

Sample Output 2

0

Sample Input 3

4 4
155374934 164163676 576823355 954291757
797829355 404011431 353195922 138996221
191890310 782177068 818008580 384836991
160449218 545531545 840594328 501899080

Sample Output 3

102