Problem Statement

Every day, N passengers arrive at Takahashi Airport. The i-th passenger arrives at time T_i.

Every passenger arrived at Takahashi airport travels to the city by bus. Each bus can accommodate up to C passengers. Naturally, a passenger cannot take a bus that departs earlier than the airplane arrives at the airport. Also, a passenger will get angry if he/she is still unable to take a bus K units of time after the arrival of the airplane. For that reason, it is necessary to arrange buses so that the i-th passenger can take a bus departing at time between T_i and T_i + K (inclusive).

When setting the departure times for buses under this condition, find the minimum required number of buses. Here, the departure time for each bus does not need to be an integer, and there may be multiple buses that depart at the same time.

Constraints

• 2 \leq N \leq 100000
• 1 \leq C \leq 10^9
• 1 \leq K \leq 10^9
• 1 \leq T_i \leq 10^9
• C, K and T_i are integers.

Sample Input 1

5 3 5
1
2
3
6
12

Sample Output 1

3

For example, the following three buses are enough:

• A bus departing at time 4.5, that carries the passengers arriving at time 2 and 3.
• A bus departing at time 6, that carries the passengers arriving at time 1 and 6.
• A bus departing at time 12, that carries the passenger arriving at time 12.

Sample Input 2

6 3 3
7
6
2
8
10
6

Sample Output 2

3

Problem Statement

Snuke found N strange creatures. Each creature has a fixed color and size. The color and size of the i-th creature are represented by i and A_i, respectively.

Every creature can absorb another creature whose size is at most twice the size of itself. When a creature of size A and color B absorbs another creature of size C and color D (C \leq 2 \times A), they will merge into one creature of size A+C and color B. Here, depending on the sizes of two creatures, it is possible that both of them can absorb the other.

Snuke has been watching these creatures merge over and over and ultimately become one creature. Find the number of the possible colors of this creature.

Constraints

• 2 \leq N \leq 100000
• 1 \leq A_i \leq 10^9
• A_i is an integer.

Sample Input 1

3
3 1 4

Sample Output 1

2

The possible colors of the last remaining creature are colors 1 and 3. For example, when the creature of color 3 absorbs the creature of color 2, then the creature of color 1 absorbs the creature of color 3, the color of the last remaining creature will be color 1.

Sample Input 2

5
1 1 1 1 1

Sample Output 2

5

There may be multiple creatures of the same size.

Sample Input 3

6
40 1 30 2 7 20

Sample Output 3

4

Problem Statement

Takahashi has received an undirected graph with N vertices, numbered 1, 2, ..., N. The edges in this graph are represented by (u_i, v_i). There are no self-loops and multiple edges in this graph.

Based on this graph, Takahashi is now constructing a new graph with N^2 vertices, where each vertex is labeled with a pair of integers (a, b) (1 \leq a \leq N, 1 \leq b \leq N). The edges in this new graph are generated by the following rule:

• Span an edge between vertices (a, b) and (a', b') if and only if both of the following two edges exist in the original graph: an edge between vertices a and a', and an edge between vertices b and b'.

How many connected components are there in this new graph?

Constraints

• 2 \leq N \leq 100,000
• 0 \leq M \leq 200,000
• 1 \leq u_i < v_i \leq N
• There exists no pair of distinct integers i and j such that u_i = u_j and v_i = v_j.

Sample Input 1

3 1
1 2

Sample Output 1

7

The graph constructed by Takahashi is as follows.

Sample Input 2

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

Sample Output 2

18

Problem Statement

Takahashi has a lot of peculiar devices. These cylindrical devices receive balls from left and right. Each device is in one of the two states A and B, and for each state, the device operates as follows:

• When a device in state A receives a ball from either side (left or right), the device throws out the ball from the same side, then immediately goes into state B.
• When a device in state B receives a ball from either side, the device throws out the ball from the other side, then immediately goes into state A.

The transition of the state of a device happens momentarily and always completes before it receives another ball.

Takahashi built a contraption by concatenating N of these devices. In this contraption,

• A ball that was thrown out from the right side of the i-th device from the left (1 \leq i \leq N-1) immediately enters the (i+1)-th device from the left side.
• A ball that was thrown out from the left side of the i-th device from the left (2 \leq i \leq N) immediately enters the (i-1)-th device from the right side.

The initial state of the i-th device from the left is represented by the i-th character in a string S. From this situation, Takahashi performed the following K times: put a ball into the leftmost device from the left side, then wait until the ball comes out of the contraption from either end. Here, it can be proved that the ball always comes out of the contraption after a finite time. Find the state of each device after K balls are processed.

Constraints

• 1 \leq N \leq 200,000
• 1 \leq K \leq 10^9
• |S|=N
• Each character in S is either A or B.

Sample Input 1

5 1
ABAAA

Sample Output 1

BBAAA

In this input, we put a ball into the leftmost device from the left side, then it is returned from the same place.

Sample Input 2

5 2
ABAAA

Sample Output 2

ABBBA

Sample Input 3

4 123456789
AABB

Sample Output 3

BABA

Problem Statement

We will call a non-negative integer increasing if, for any two adjacent digits in its decimal representation, the digit to the right is greater than or equal to the digit to the left. For example, 1558, 11, 3 and 0 are all increasing; 10 and 20170312 are not.

Snuke has an integer N. Find the minimum number of increasing integers that can represent N as their sum.

Constraints

• 1 \leq N \leq 10^{500000}

Sample Input 1

80

Sample Output 1

2

One possible representation is 80 = 77 + 3.

Sample Input 2

123456789

Sample Output 2

1

123456789 in itself is increasing, and thus it can be represented as the sum of one increasing integer.

Sample Input 3

20170312

Sample Output 3

4

Sample Input 4

7204647845201772120166980358816078279571541735614841625060678056933503

Sample Output 4

31

Problem Statement

There is a railroad in Takahashi Kingdom. The railroad consists of N sections, numbered 1, 2, ..., N, and N+1 stations, numbered 0, 1, ..., N. Section i directly connects the stations i-1 and i. A train takes exactly A_i minutes to run through section i, regardless of direction. Each of the N sections is either single-tracked over the whole length, or double-tracked over the whole length. If B_i = 1, section i is single-tracked; if B_i = 2, section i is double-tracked. Two trains running in opposite directions can cross each other on a double-tracked section, but not on a single-tracked section. Trains can also cross each other at a station.

Snuke is creating the timetable for this railroad. In this timetable, the trains on the railroad run every K minutes, as shown in the following figure. Here, bold lines represent the positions of trains running on the railroad. (See Sample 1 for clarification.)

When creating such a timetable, find the minimum sum of the amount of time required for a train to depart station 0 and reach station N, and the amount of time required for a train to depart station N and reach station 0. It can be proved that, if there exists a timetable satisfying the conditions in this problem, this minimum sum is always an integer.

Formally, the times at which trains arrive and depart must satisfy the following:

• Each train either departs station 0 and is bound for station N, or departs station N and is bound for station 0.
• Each train takes exactly A_i minutes to run through section i. For example, if a train bound for station N departs station i-1 at time t, the train arrives at station i exactly at time t+A_i.
• Assume that a train bound for station N arrives at a station at time s, and departs the station at time t. Then, the next train bound for station N arrives at the station at time s+K, and departs the station at time t+K. Additionally, the previous train bound for station N arrives at the station at time s-K, and departs the station at time t-K. This must also be true for trains bound for station 0.
• Trains running in opposite directions must not be running on the same single-tracked section (except the stations at both ends) at the same time.

Constraints

• 1 \leq N \leq 100000
• 1 \leq K \leq 10^9
• 1 \leq A_i \leq 10^9
• A_i is an integer.
• B_i is either 1 or 2.

Partial Score

• In the test set worth 500 points, all the sections are single-tracked. That is, B_i = 1.
• In the test set worth another 500 points, N \leq 200.

Sample Input 1

3 10
4 1
3 1
4 1

Sample Output 1

26

For example, the sum of the amount of time in question will be 26 minutes in the following timetable:

In this timetable, the train represented by the red line departs station 0 at time 0, arrives at station 1 at time 4, departs station 1 at time 5, arrives at station 2 at time 8, and so on.

Sample Input 2

1 10
10 1

Sample Output 2

-1

Sample Input 3

6 4
1 1
1 1
1 1
1 1
1 1
1 1

Sample Output 3

12

Sample Input 4

20 987654321
129662684 2
162021979 1
458437539 1
319670097 2
202863355 1
112218745 1
348732033 1
323036578 1
382398703 1
55854389 1
283445191 1
151300613 1
693338042 2
191178308 2
386707193 1
204580036 1
335134457 1
122253639 1
824646518 2
902554792 2

Sample Output 4

14829091348