Problem Statement

You are given an integer N between 0 and 9999 (inclusive).

Print it as a four-digit string after appending to it the necessary number of leading zeros.

Constraints

• 0 \leq N \leq 9999
• N is an integer.

Sample Input 1

321

Sample Output 1

0321

321 has three digits, so we need to add one leading zero to it to make it have four digits.

Sample Input 2

7777

Sample Output 2

7777

Sample Input 3

1

Sample Output 3

0001

Problem Statement

You are given a positive integer N.

For i=1,2,\ldots,N, calculate (-1)^i \times i^3, and find the sum of these N values.

That is, find \displaystyle \sum_{i=1}^N (-1)^i \times i^3.

Constraints

• N is an integer between 1 and 10, inclusive.

Sample Input 1

3

Sample Output 1

-20

• When i=1: (-1)^i\times i^3=-1.
• When i=2: (-1)^i\times i^3=8.
• When i=3: (-1)^i\times i^3=-27.

Therefore, output -1 + 8 - 27 = -20.

Sample Input 2

9

Sample Output 2

-425

Sample Input 3

10

Sample Output 3

575

Problem Statement

Given a positive integer N, find the maximum integer k such that 2^k \le N.

Constraints

• N is an integer satisfying 1 \le N \le 10^{18}.

Sample Input 1

6

Sample Output 1

2

• k=2 satisfies 2^2=4 \le 6.
• For every integer k such that k \ge 3, 2^k > 6 holds.

Therefore, the answer is k=2.

Sample Input 2

1

Sample Output 2

0

Note that 2^0=1.

Sample Input 3

1000000000000000000

Sample Output 3

59

The input value may not fit into a 32-bit integer.

Problem Statement

Two dice, each with six faces 1,2,3,4,5,6, are rolled. Find the probability that at least one of the following two conditions holds:

• The sum of the two outcomes is at least X.
• The absolute difference of the two outcomes is at least Y.

Each face of each die is equally likely, and the two dice are independent.

Constraints

• 2 \le X \le 13
• 0 \le Y \le 6
• All input values are integers.

Sample Input 1

9 3

Sample Output 1

0.555555555555555555555555555555

Let (x,y) denote the event that the dice show x and y.

• The sum is at least 9 for (3,6),(4,5),(4,6),(5,4),(5,5),(5,6),(6,3),(6,4),(6,5),(6,6).
• The difference is at least 3 for (1,4),(1,5),(1,6),(2,5),(2,6),(3,6),(4,1),(5,1),(5,2),(6,1),(6,2),(6,3).

At least one of these conditions holds for the following 20 pairs: (1,4),(1,5),(1,6),(2,5),(2,6),(3,6),(4,1),(4,5),(4,6),(5,1),(5,2),(5,4),(5,5),(5,6),(6,1),(6,2),(6,3),(6,4),(6,5),(6,6).

Thus, the answer is \dfrac{20}{36}=\dfrac59=0.5555555555\ldots.

Because an absolute error of at most 10^{-9} is allowed, outputs such as 0.5555555565 or 0.55555555456789 are accepted.

Sample Input 2

13 6

Sample Output 2

0

Neither the sum of two dice can be 13 or greater, nor can their difference be 6 or greater.

Thus, the answer is 0.

Sample Input 3

10 3

Sample Output 3

0.5

Problem Statement

There are N dishes, and the i-th dish has a sweetness of A_i and a saltiness of B_i.

Takahashi plans to arrange these N dishes in any order he likes and eat them in that order.

He will eat the dishes in the arranged order, but he will stop eating as soon as the total sweetness of the dishes he has eaten exceeds X or the total saltiness exceeds Y.

Find the minimum possible number of dishes that he will end up eating.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq X, Y \leq 2 \times 10^{14}
• 1 \leq A_i, B_i \leq 10^9
• All input values are integers.

Sample Input 1

4 7 18
2 3 5 1
8 8 1 4

Sample Output 1

2

The i-th dish will be denoted as dish i.

If he arranges the four dishes in the order 2, 3, 1, 4, as soon as he eats dishes 2 and 3, their total sweetness is 8, which is greater than 7. Therefore, in this case, he will end up eating two dishes.

The number of dishes he will eat cannot be 1 or less, so print 2.

Sample Input 2

5 200000000000000 200000000000000
1 1 1 1 1
2 2 2 2 2

Sample Output 2

5

Sample Input 3

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

Sample Output 3

6

Problem Statement

There are N people, each of whom is either a child or an adult. The i-th person has a weight of W_i.
Whether each person is a child or an adult is specified by a string S of length N consisting of 0 and 1.
If the i-th character of S is 0, then the i-th person is a child; if it is 1, then the i-th person is an adult.

When Takahashi the robot is given a real number X, Takahashi judges a person with a weight less than X to be a child and a person with a weight more than or equal to X to be an adult.
For a real value X, let f(X) be the number of people whom Takahashi correctly judges whether they are children or adults.

Find the maximum value of f(X) for all real values of X.

Constraints

• 1\leq N\leq 2\times 10^5
• S is a string of length N consisting of 0 and 1.
• 1\leq W_i\leq 10^9
• N and W_i are integers.

Sample Input 1

5
10101
60 45 30 40 80

Sample Output 1

4

When Takahashi is given X=50, it judges the 2-nd, 3-rd, and 4-th people to be children and the 1-st and 5-th to be adults.
In reality, the 2-nd and 4-th are children, and the 1-st, 3-rd, and 5-th are adults, so the 1-st, 2-nd, 4-th, and 5-th people are correctly judged. Thus, f(50)=4.

This is the maximum since there is no X that judges correctly for all 5 people. Thus, 4 should be printed.

Sample Input 2

3
000
1 2 3

Sample Output 2

3

For example, X=10 achieves the maximum value f(10)=3.
Note that the people may be all children or all adults.

Sample Input 3

5
10101
60 50 50 50 60

Sample Output 3

4

For example, X=55 achieves the maximum value f(55)=4.
Note that there may be multiple people with the same weight.

Problem Statement

In a town divided into a grid with N rows and 10^9 columns, there are N walls, numbered 1 to N.
Wall i ranges from the L_i-th column to the R_i-th column from the left in the i-th row from the top. (See also the figure at Sample Input and Output 1.)

Takahashi has decided to destroy all N walls.
With his superhuman strength, his one punch can damage consecutive D columns at once.

• More formally, he can choose an integer x between 1 and 10^9 - D + 1 (inclusive) to damage all walls that exist (or partly exist) in the x-th through (x + D - 1)-th columns and are not yet destroyed.

When a part of a wall is damaged, that whole wall will be destroyed by the impact of the punch.
(See also the figure at Sample Input and Output 1.)

At least how many times does Takahashi need to punch to destroy all walls?

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq D \leq 10^9
• 1 \leq L_i \leq R_i \leq 10^9
• All values in input are integers.

Sample Input 1

3 3
1 2
4 7
5 9

Sample Output 1

2

The figure below describes the arrangements of walls in Sample Input 1.

He can destroy all walls with two punches, such as the following. (Below, \lbrack a, b \rbrack denotes the range from the a-th through b-th columns.)

• First, punch \lbrack 2, 4 \rbrack. The walls existing in \lbrack 2, 4 \rbrack ― Walls 1 and 2 ― are damaged and destroyed.
• Second, punch \lbrack 5, 7 \rbrack. The wall existing in \lbrack 5, 7 \rbrack ― Wall 3 ― is damaged and destroyed.

It is also possible to destroy all walls with two punches in this way:

• First, punch \lbrack 7, 9 \rbrack to destroy Walls 2 and 3.
• Second, punch \lbrack 1, 3 \rbrack to destroy Wall 1.

Sample Input 2

3 3
1 2
4 7
4 9

Sample Output 2

1

The difference from Sample Input/Output 1 is that Wall 3 now covers \lbrack 4, 9 \rbrack, not \lbrack 5, 9 \rbrack.
In this case, he can punch \lbrack 2, 4 \rbrack to destroy all walls with one punch.

Sample Input 3

5 2
1 100
1 1000000000
101 1000
9982 44353
1000000000 1000000000

Sample Output 3

3

Problem Statement

You are given a directed graph with N vertices and M edges. The i-th edge (1 \leq i \leq M) is a directed edge from vertex u _ i to vertex v _ i.

Initially, you are at vertex 1. You want to repeat the following operations until you reach vertex N:

• Perform one of the two operations below:
  • Move along a directed edge from your current vertex. This incurs a cost of 1. More precisely, if you are at vertex v, choose a vertex u such that there is a directed edge from v to u, and move to vertex u.
  • Reverse the direction of all edges. This incurs a cost of X. More precisely, if and only if there was a directed edge from v to u immediately before this operation, there is a directed edge from u to v immediately after this operation.

It is guaranteed that, for the given graph, you can reach vertex N from vertex 1 by repeating these operations.

Find the minimum total cost required to reach vertex N.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq X \leq 10^9
• 1 \leq u _ i \leq N \ (1 \leq i \leq M)
• 1 \leq v _ i \leq N \ (1 \leq i \leq M)
• For the given graph, it is guaranteed that you can reach vertex N from vertex 1 by the operations described.
• All input values are integers.

Sample Input 1

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

Sample Output 1

4

The given graph looks like this:

You can reach vertex 5 with a total cost of 4 by doing the following:

• Move to vertex 2 at a cost of 1.
• Move to vertex 4 at a cost of 1.
• Move to vertex 3 at a cost of 1.
• Move to vertex 5 at a cost of 1.

It is impossible to reach vertex 5 with a total cost of 3 or less, so print 4.

Sample Input 2

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

Sample Output 2

3

The graph is the same as in Sample 1, but the cost to reverse edges is different.

You can reach vertex 5 with a total cost of 3 as follows:

• Move to vertex 2 at a cost of 1.
• Reverse all edges at a cost of 1.
• Move to vertex 5 at a cost of 1.

It is impossible to reach vertex 5 with a total cost of 2 or less, so print 3.

Sample Input 3

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

Sample Output 3

4294967299

Note that the answer may exceed the 32-bit integer range.

Sample Input 4

20 13 5
1 3
14 18
18 17
12 19
3 5
4 6
13 9
8 5
14 2
20 18
8 14
4 9
14 8

Sample Output 4

21

Problem Statement

You are given a string S of length N consisting of lowercase English letters.
Process Q queries described below in the order they are given.
There are two types of queries:

• 1 x c : Change the x-th character of S to the lowercase English letter c.
• 2 L R : If the substring formed by the L-th through R-th characters of S is a palindrome, print Yes; otherwise, print No.

Constraints

• 1 \leq N \leq 10^6
• 1 \leq Q \leq 10^5
• S is a string of length N consisting of lowercase English letters.
• 1 \leq x \leq N
• c is a lowercase English letter.
• 1 \leq L \leq R \leq N
• N, Q, x, L, R are integers.

Sample Input 1

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

Sample Output 1

Yes
No
Yes
No
Yes
Yes

Initially, S = abcbacb.
For the first query, the string formed by the 1-st through 5-th characters of S is abcba, which is a palindrome. Thus, print Yes.
For the second query, the string formed by the 4-th through 7-th character of S is bacb, which is not a palindrome. Thus, print No.
For the third query, the string formed by the 2-nd through 2-nd character of S is b, which is a palindrome. Thus, output Yes.
For the fourth query, change the 5-th character of S to c. S becomes abcbccb.
For the fifth query, the string formed by the 1-st through 5-th character of S is abcbc, which is not a palindrome. Thus, output No.
For the sixth query, the string formed by the 4-th through 7-th character of S is bccb, which is a palindrome. Thus, output Yes.
For the seventh query, change the 4-th character of S to c. S becomes abccccb.
For the eighth query, the string formed by the 3-rd through 6-th character of cccc, which is a palindrome. Thus, output Yes.