Problem Statement

You are given an integer N at least 100. Print the last two digits of N.

Strictly speaking, print the tens and ones digits of N in this order.

Constraints

• 100 \le N \le 999
• N is an integer.

Sample Input 1

254

Sample Output 1

54

The last two digits of 254 are 54, which should be printed.

Sample Input 2

101

Sample Output 2

01

The last two digits of 101 are 01, which should be printed.

Problem Statement

There is an enemy with stamina A. Every time you attack the enemy, its stamina reduces by B.

At least how many times do you need to attack the enemy to make its stamina 0 or less?

Constraints

• 1 \le A,B \le 10^{18}
• A and B are integers.

Sample Input 1

7 3

Sample Output 1

3

Attacking three times make the enemy's stamina -2.

Attacking only twice makes the stamina 1, so you need to attack it three times.

Sample Input 2

123456789123456789 987654321

Sample Output 2

124999999

Sample Input 3

999999999999999998 2

Sample Output 3

499999999999999999

Problem Statement

There were N contestants in the qualification round of a programming contest. All contestants got distinct ranks.
You are given a length-N string S, which represents whether the contestants want to participate in the final round or not. Specifically,

• if the i-th character of S is o, the contestant ranked i-th in the qualification wants to participate in the final;
• if the i-th character of S is x, the contestant ranked i-th in the qualification does not want to participate in the final.

Among those who want to participate in the final, K contestants with the smallest ranks advance to the final.

Print a string T of length N that satisfies the following conditions:

• if the contestant ranked i-th in the qualification advances to the final, the i-th character of T is o;
• if the contestant ranked i-th in the qualification does not advance to the final, the i-th character of T is x.

Constraints

• N and K are integers.
• 1 \le K \le N \le 100
• S is a string of length N consisting of o and x.
• S has at least K o's.

Sample Input 1

10 3
oxxoxooxox

Sample Output 1

oxxoxoxxxx

In this input, N=10 people took part in the qualification round, and K=3 of them advance to the final.

• The participant who ranked 1-st in the qualification wants to participate in the final, so the participant advances to the final. 1 participant has advanced so far.
• The participants who ranked 2-nd and 3-rd in the qualification do not want to participate in the final, so the participants do not advance to the final.
• The participant who ranked 4-th in the qualification wants to participate in the final, so the participant advances to the final. 2 participants have advanced so far.
• The participants who ranked 5-th in the qualification does not want to participate in the final, so the participant does not advance to the final.
• The participant who ranked 6-th in the qualification wants to participate in the final, so the participant advances to the final. 3 participants have advanced so far.
• Now that 3 people have advanced to the final, no participants ranked 7-th or lower advance to the final.

Problem Statement

Takahashi has a string S consisting of lowercase English letters.

On this string, he will do the operation below just once.

• First, choose a non-negative integer K.
• Then, shift each character of S to the right by K (see below).

Here,

• a shifted to the right by 1 is b;
• b shifted to the right by 1 is c;
• c shifted to the right by 1 is d;
• \cdots
• y shifted to the right by 1 is z;
• z shifted to the right by 1 is a.

For example, b shifted to the right by 4 is f, and y shifted to the right by 3 is b.

You are given a string T. Determine whether Takahashi can make S equal T by the operation above.

Constraints

• Each of S and T is a string of length between 1 and 10^5 (inclusive) consisting of lowercase English letters.
• The lengths of S and T are equal.

Sample Input 1

abc
ijk

Sample Output 1

Yes

When Takahashi chooses K=8,

• a is shifted to the right by 8 and becomes i,
• b is shifted to the right by 8 and becomes j,
• c is shifted to the right by 8 and becomes k,

and now S and T are equal.
Therefore, he can make S equal T, so Yes should be printed.

Sample Input 2

z
a

Sample Output 2

Yes

Choosing K=1 makes S and T equal.
Note that the letter on the right of z is a.

Sample Input 3

ppq
qqp

Sample Output 3

No

There is no non-negative integer K that he can choose to make S equal T, so No should be printed.

Sample Input 4

atcoder
atcoder

Sample Output 4

Yes

Choosing K=0 makes S and T equal.

Problem Statement

You are given a string S of length N consisting of lowercase English letters. Each character of S is painted in one of the M colors: color 1, color 2, ..., color M; for each i = 1, 2, \ldots, N, the i-th character of S is painted in color C_i.

For each i = 1, 2, \ldots, M in this order, let us perform the following operation.

• Perform a right circular shift by 1 on the part of S painted in color i. That is, if the p_1-th, p_2-th, p_3-th, \ldots, p_k-th characters are painted in color i from left to right, then simultaneously replace the p_1-th, p_2-th, p_3-th, \ldots, p_k-th characters of S with the p_k-th, p_1-th, p_2-th, \ldots, p_{k-1}-th characters of S, respectively.

Print the final S after the above operations.

The constraints guarantee that at least one character of S is painted in each of the M colors.

Constraints

• 1 \leq M \leq N \leq 2 \times 10^5
• 1 \leq C_i \leq M
• N, M, and C_i are all integers.
• S is a string of length N consisting of lowercase English letters.
• For each integer 1 \leq i \leq M, there is an integer 1 \leq j \leq N such that C_j = i.

Sample Input 1

8 3
apzbqrcs
1 2 3 1 2 2 1 2

Sample Output 1

cszapqbr

Initially, S = apzbqrcs.

• For i = 1, perform a right circular shift by 1 on the part of S formed by the 1-st, 4-th, 7-th characters, resulting in S = cpzaqrbs.
• For i = 2, perform a right circular shift by 1 on the part of S formed by the 2-nd, 5-th, 6-th, 8-th characters, resulting in S = cszapqbr.
• For i = 3, perform a right circular shift by 1 on the part of S formed by the 3-rd character, resulting in S = cszapqbr (here, S is not changed).

Thus, you should print cszapqbr, the final S.

Sample Input 2

2 1
aa
1 1

Sample Output 2

aa

Problem Statement

You are given a positive integer N.

Find the number of triples of positive integers (A, B, C) such that A\leq B\leq C and ABC\leq N.

The Constraints guarantee that the answer is less than 2^{63}.

Constraints

• 1 \leq N \leq 10^{11}
• N is an integer.

Sample Input 1

4

Sample Output 1

5

There are five such triples: (1,1,1),(1,1,2),(1,1,3),(1,1,4),(1,2,2).

Sample Input 2

100

Sample Output 2

323

Sample Input 3

100000000000

Sample Output 3

5745290566750

Problem Statement

The string 20230322 can be rearranged into 02320232, which is a repetition of 0232 twice.
Similarly, a string consisting of digits is said to be happy when it can be rearranged into (or already is) a repetition of some string twice.
You are given a string S consisting of digits. Find the number of pairs of integers (l,r) satisfying all of the following conditions.

• 1 \le l \le r \le |S|. (|S| is the length of S.)
• The (contiguous) substring formed of the l-th through r-th characters of S is happy.

Constraints

• S is a string consisting of digits whose length is between 1 and 5 \times 10^5, inclusive.

Sample Input 1

20230322

Sample Output 1

4

We have S= 20230322.

Here are the four pairs of integers (l,r) that satisfy the condition: (1,6), (1,8), (2,7), and (7,8).

Sample Input 2

0112223333444445555556666666777777778888888889999999999

Sample Output 2

185

S may begin with 0.

Sample Input 3

3141592653589793238462643383279502884197169399375105820974944

Sample Output 3

9

Problem Statement

There are villages at some number of points in the xy-plane.
Takahashi will construct a moat to protect these villages from enemies such as civil armies and witches.

You are given a 4 \times 4 matrix A = (A_{i, j}) consisting of 0 and 1.
For each pair of integers (i, j) (1 \leq i, j \leq 4) such that A_{i, j} = 1, there is a village at the coordinates (i-0.5, j-0.5).

The moat will be a polygon in the plane. Takahashi will construct it so that the following conditions will be satisfied. (See also the annotation at Sample Input/Output 1.)

1. There is no self-intersection.
2. All villages are contained in the interior of the polygon.
3. The x- and y-coordinates of every vertex are integers between 0 and 4 (inclusive).
4. Every edge is parallel to the x- or y-axis.
5. Every inner angle is 90 or 270 degrees.

Print the number of ways in which Takahashi can construct the moat.

Constraints

• A_{i, j} \in \lbrace 0, 1\rbrace
• There is at least one pair (i, j) such that A_{i, j} = 1.

Sample Input 1

1 0 0 0
0 0 1 0
0 0 0 0
1 0 0 0

Sample Output 1

1272

The two ways to construct the moat shown in the images below are valid.

The four ways to construct the moat shown in the images below are invalid.

Here are the reasons the above ways are invalid.

• The first way violates the condition: "There is no self-intersection."
• The second way violates the condition: "All villages are contained in the interior of the polygon."
• The third way violates the condition: "The x- and y-coordinates of every vertex are integers between 0 and 4." (Some vertices have non-integer coordinates.)
• The fourth way violates the condition: "Every edge is parallel to the x- or y-axis."

Sample Input 2

1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

Sample Output 2

1

Problem Statement

The roads in the Kingdom of AtCoder, which lies on the xy-plane, are the lines x=n and y=n for all integers n. Among them, the lines x=Bn and y=Bn for all integers n are main roads.

When Takahashi is at (x,y), he can move to (x,y-1), (x,y+1), (x+1,y), or (x-1,y). Each move takes 1 second along a main road and K seconds otherwise.

Find the minimum number of seconds Takahashi needs to get from (S_x, S_y) to (G_x, G_y).

You will have T test cases to solve.

Constraints

• 1 \le T \le 2 \times 10^5
• 1 \le B,K \le 10^9
• 0 \le S_x,S_y,G_x,G_y \le 10^9
• All values in input are integers.

Sample Input 1

4
3 4 2 2 4 4
5 6 2 3 2 3
1 1000000000 0 0 1000000000 1000000000
1000000000 1000000000 500000000 500000000 1000000000 1000000000

Sample Output 1

10
0
2000000000
500000000500000000

For the 1-st test case, he can go from (2,2) to (2,3) in 4 seconds, from (2,3) to (4,3) in 2 seconds, and from (4,3) to (4,4) in 4 seconds to get from (2,2) to (4,4) in 10 seconds. It is impossible to get there in less than 10 seconds, so the answer is 10.
For the 2-nd test case, he is already at (G_x, G_y) in the beginning, so the answer is 0.

Sample Input 2

10
928184439 674654465 203937094 186855052 851783856 805293696
55480262 448852233 823161539 786348805 550018803 322680316
891870741 235679524 32164572 497841190 620600021 96487871
321502816 428964257 499656016 521484999 717623189 824784374
144040837 680268887 76238777 371138006 350230937 78690135
768922620 799628518 403830696 60449731 218880692 88319939
482031503 121412614 472330444 284479575 949635609 427232765
389524418 132987043 656496997 678732442 23028233 488463974
857778764 629964237 714551548 739330018 579247790 874251485
461612428 535402609 555160129 833592114 44418273 287363785

Sample Output 2

177606591118701316
6205925075792263
30320747646118343
84136273267803188
83764071874751489
118960470930399064
2929499649126153
16403238161749820
84995699148879437
71771264361119335