Problem Statement

Takahashi turned on a computer at time 0 and clicked the mouse N times. The i-th (1 \le i \le N) click was at time T_i.

If he consecutively clicked the mouse at time x_1 and time x_2 (where x_1 < x_2), a double click is said to be fired at time x_2 if and only if x_2 - x_1 \le D.

What time was a double click fired for the first time? If no double click was fired, print -1 instead.

Constraints

• 1 \le N \le 100
• 1 \le D \le 10^9
• 1 \le T_i \le 10^9(1 \le i \le N)
• T_i < T_{i+1}(1 \le i \le N-1)
• All values in the input are integers.

Sample Input 1

4 500
300 900 1300 1700

Sample Output 1

1300

Takahashi clicked the mouse at time 900 and 1300. Since 1300 - 900 \le 500, a double click was fired at time 1300.

A double click had not been fired before time 1300, so 1300 should be printed.

Sample Input 2

5 99
100 200 300 400 500

Sample Output 2

-1

No double click was fired, so print -1.

Sample Input 3

4 500
100 600 1100 1600

Sample Output 3

600

If multiple double clicks were fired, be sure to print only the first such event.

Problem Statement

You are given a 6-digit positive integer N.
Determine whether N satisfies all of the following conditions.

• Among the digits of N, the digit 1 appears exactly once.
• Among the digits of N, the digit 2 appears exactly twice.
• Among the digits of N, the digit 3 appears exactly three times.

Constraints

• N is an integer satisfying 100000 \le N \le 999999.

Sample Input 1

123233

Sample Output 1

Yes

123233 satisfies the conditions in the problem statement, so print Yes.

Sample Input 2

123234

Sample Output 2

No

123234 does not satisfy the conditions in the problem statement, so print No.

Sample Input 3

323132

Sample Output 3

Yes

Sample Input 4

500000

Sample Output 4

No

Problem Statement

You are given a string S consisting of . and #.

Among all strings T that satisfy all of the following conditions, find one with the maximum number of os.

• The length of T is equal to the length of S.
• T consists of ., #, or o.
• T_i= # if and only if S_i= #.
• If T_i=T_j= o (i < j), then there exists at least one # among T_{i+1},\ldots,T_{j-1}.

Constraints

• S is a string consisting of . and # with length between 1 and 100, inclusive.

Sample Input 1

#..#.

Sample Output 1

#o.#o

Setting T= #o.#o satisfies all conditions.

There is no string T that satisfies all conditions and has more than two os, so outputting #o.#o is correct.

Outputting #.o#o is also correct.

Sample Input 2

#

Sample Output 2

#

Sample Input 3

.....

Sample Output 3

..o..

Outputting o...., .o..., ...o., or ....o is also correct.

Sample Input 4

...#..#.##.#.

Sample Output 4

o..#.o#o##o#o

Problem Statement

Studying Kanbun, Takahashi is having trouble figuring out the order to read words. Help him out!

There are N integers from 1 through N arranged in a line in ascending order.
Between them are M "レ" marks. The i-th "レ" mark is between the integer a_i and integer (a_i + 1).

You read each of the N integers once by the following procedure.

• Consider an undirected graph G with N vertices numbered 1 through N and M edges. The i-th edge connects vertex a_i and vertex (a_i+1).
• Repeat the following operation until there is no unread integer:
  • let x be the minimum unread integer. Choose the connected component C containing vertex x, and read all the numbers of the vertices contained in C in descending order.

For example, suppose that integers and "レ" marks are arranged in the following order:

(In this case, N = 5, M = 3, and a = (1, 3, 4).)
Then, the order to read the integers is determined to be 2, 1, 5, 4, and 3, as follows:

• At first, the minimum unread integer is 1, and the connected component of G containing vertex 1 has vertices \lbrace 1, 2 \rbrace, so 2 and 1 are read in this order.
• Then, the minimum unread integer is 3, and the connected component of G containing vertex 3 has vertices \lbrace 3, 4, 5 \rbrace, so 5, 4, and 3 are read in this order.
• Now that all integers are read, terminate the procedure.

Given N, M, and (a_1, a_2, \dots, a_M), print the order to read the N integers.

Constraints

• 1 \leq N \leq 100
• 0 \leq M \leq N - 1
• 1 \leq a_1 \lt a_2 \lt \dots \lt a_M \leq N-1
• All values in the input are integers.

Sample Input 1

5 3
1 3 4

Sample Output 1

2 1 5 4 3

As described in the Problem Statement, if integers and "レ" marks are arranged in the following order:

then the integers are read in the following order: 2, 1, 5, 4, and 3.

Sample Input 2

5 0

Sample Output 2

1 2 3 4 5

There may be no "レ" mark.

Sample Input 3

10 6
1 2 3 7 8 9

Sample Output 3

4 3 2 1 5 6 10 9 8 7

Problem Statement

At the entrance of AtCoder Inc., there is a special pass-code input device. The device consists of a screen displaying one string, and two buttons.

Let t be the string shown on the screen. Initially, t is the empty string. Pressing a button changes t as follows:

• Pressing button A appends 0 to the end of t.
• Pressing button B replaces every digit in t with the next digit: for digits 0 through 8 the next digit is the one whose value is larger by 1; the next digit after 9 is 0.

For example, if t is 1984 and button A is pressed, t becomes 19840; if button B is then pressed, t becomes 20951.

You are given a string S. Starting from the empty string, press the buttons zero or more times until t coincides with S. Find the minimum number of button presses required.

Constraints

• S is a string consisting of 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9.
• 1 \le |S| \le 5 \times 10^{5}, where |S| is the length of S.

Sample Input 1

21

Sample Output 1

4

The following sequence of presses makes t equal to 21.

1. Press button A. t becomes 0.
2. Press button B. t becomes 1.
3. Press button A. t becomes 10.
4. Press button B. t becomes 21.

It is impossible to obtain 21 with fewer than four presses, so output 4.

Sample Input 2

407

Sample Output 2

17

Sample Input 3

2025524202552420255242025524

Sample Output 3

150

Problem Statement

AtCoder Inc. sells T-shirts with its logo.

You are given Takahashi's schedule for N days as a string S of length N consisting of 0, 1, and 2.
Specifically, for an integer i satisfying 1\leq i\leq N,

• if the i-th character of S is 0, he has no plan scheduled for the i-th day;
• if the i-th character of S is 1, he plans to go out for a meal on the i-th day;
• if the i-th character of S is 2, he plans to attend a competitive programming event on the i-th day.

Takahashi has M plain T-shirts, all washed and ready to wear just before the first day.
In addition, to be able to satisfy the following conditions, he will buy several AtCoder logo T-shirts.

• On days he goes out for a meal, he will wear a plain or logo T-shirt.
• On days he attends a competitive programming event, he will wear a logo T-shirt.
• On days with no plans, he will not wear any T-shirts. Also, he will wash all T-shirts worn at that point. He can wear them again from the next day onwards.
• Once he wears a T-shirt, he cannot wear it again until he washes it.

Determine the minimum number of T-shirts he needs to buy to be able to wear appropriate T-shirts on all scheduled days during the N days. If he does not need to buy new T-shirts, print 0.
Assume that the purchased T-shirts are also washed and ready to use just before the first day.

Constraints

• 1\leq M\leq N\leq 1000
• S is a string of length N consisting of 0, 1, and 2.
• N and M are integers.

Sample Input 1

6 1
112022

Sample Output 1

2

If Takahashi buys two logo T-shirts, he can wear T-shirts as follows:

• On the first day, he wears a logo T-shirt to go out for a meal.
• On the second day, he wears a plain T-shirt to go out for a meal.
• On the third day, he wears a logo T-shirt to attend a competitive programming event.
• On the fourth day, he has no plans, so he washes all the worn T-shirts. This allows him to reuse the T-shirts worn on the first, second, and third days.
• On the fifth day, he wears a logo T-shirt to attend a competitive programming event.
• On the sixth day, he wears a logo T-shirt to attend a competitive programming event.

If he buys one or fewer logo T-shirts, he cannot use T-shirts to meet the conditions no matter what. Hence, print 2.

Sample Input 2

3 1
222

Sample Output 2

3

Sample Input 3

2 1
01

Sample Output 3

0

He does not need to buy new T-shirts.

Problem Statement

There is a restaurant that can accommodate at most K customers simultaneously. In front of this restaurant, there is a side street where one queue is managed.

At time 0, there are no customers in the restaurant, and the queue is also empty.

Today, N groups of customers are scheduled to come, and they are numbered from 1 to N in the order of their arrival. Group i consists of C_i people, joins the end of the queue at time A_i, and leaves the restaurant B_i time units after entering.

Each group enters the restaurant by leaving the queue at the earliest time when both of the following two conditions are satisfied simultaneously:

• The group is at the front of the queue. In other words, the group is the earliest to have joined among those still in the queue at that point.
• When the number of people in that group and all groups currently in the restaurant (including those entering at exactly that time and excluding those leaving) are combined, there are K or fewer people.

Find the time when each group enters the restaurant.

Constraints

• 1 \leq N \leq 3 \times 10^5
• 1 \leq K \leq 10^7
• 1 \leq A_i, B_i \leq 10^7 (1 \leq i \leq N)
• A_1 < \dots < A_N
• 1 \leq C_i \leq K (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

4 10
30 300 3
60 45 4
90 45 5
120 45 2

Sample Output 1

30
60
105
120

The entry and exit of each group proceed as follows:

• At time 30, group 1 joins the queue and immediately enters, making the number of customers in the restaurant 3.
• At time 60, group 2 joins the queue and immediately enters, making the number of customers in the restaurant 7.
• At time 90, group 3 joins the queue.
• At time 105, group 2 leaves, making the number of customers in the restaurant 3. Immediately after, group 3 enters, making the number of customers in the restaurant 8.
• At time 120, group 4 joins the queue and immediately enters, making the number of customers in the restaurant 10.
• At time 150, group 3 leaves, making the number of customers in the restaurant 5.
• At time 165, group 4 leaves, making the number of customers in the restaurant 3.
• At time 330, group 1 leaves, making the number of customers in the restaurant 0.

Sample Input 2

4 10
30 300 10
60 45 2
90 45 3
120 45 4

Sample Output 2

30
330
330
330

The entry and exit of each group proceed as follows:

• At time 30, group 1 joins the queue and immediately enters, making the number of customers in the restaurant 10.
• At time 60, group 2 joins the queue.
• At time 90, group 3 joins the queue.
• At time 120, group 4 joins the queue.
• At time 330, group 1 leaves, making the number of customers in the restaurant 0. Immediately after, groups 2,3,4 enter, making the number of customers in the restaurant 9.
• At time 375, groups 2,3,4 leave, making the number of customers in the restaurant 0.

Sample Input 3

10 24
279290 9485601 1
1094410 8022270 4
1314176 7214745 5
1897674 5924694 10
1921802 5769841 4
2506394 2765234 2
2558629 2727489 9
2681289 4061363 5
3022540 2291905 3
4407692 1313036 8

Sample Output 3

279290
1094410
1314176
1897674
1921802
7691643
7822368
8528921
8528921
10549857

Problem Statement

There is a grid with H rows and W columns. Initially, all cells are painted with color 0.

You will perform the following operations in the order i = 1, 2, \ldots, M.

• If T_i = 1, repaint all cells in the A_i-th row with color X_i.

• If T_i = 2, repaint all cells in the A_i-th column with color X_i.

After all operations are completed, for each color i that exists on the grid, find the number of cells that are painted with color i.

Constraints

• 1 \leq H, W, M \leq 2 \times 10^5
• T_i \in \lbrace 1, 2 \rbrace
• 1 \leq A_i \leq H for each i such that T_i = 1,
• 1 \leq A_i \leq W for each i such that T_i = 2.
• 0 \leq X_i \leq 2 \times 10^5
• All input values are integers.

Sample Input 1

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

Sample Output 1

3
0 5
2 4
5 3

The operations will change the colors of the cells in the grid as follows:

0000   0000   0000   0000   0000
0000 → 5555 → 5550 → 5550 → 5550 
0000   0000   0000   3333   2222

Eventually, there are five cells painted with color 0, four with color 2, and three with color 5.

Sample Input 2

1 1 5
1 1 1
1 1 10
2 1 100
1 1 1000
2 1 10000

Sample Output 2

1
10000 1

Sample Input 3

5 5 10
1 1 1
1 2 2
1 3 3
1 4 4
1 5 5
2 1 6
2 2 7
2 3 8
2 4 9
2 5 10

Sample Output 3

5
6 5
7 5
8 5
9 5
10 5

Problem Statement

You are given a simple connected undirected graph with N vertices and M edges. (A graph is said to be simple if it has no multi-edges and no self-loops.)
For i = 1, 2, \ldots, M, the i-th edge connects Vertex u_i and Vertex v_i.

A sequence (A_1, A_2, \ldots, A_k) is said to be a path of length k if both of the following two conditions are satisfied:

• For all i = 1, 2, \dots, k, it holds that 1 \leq A_i \leq N.
• For all i = 1, 2, \ldots, k-1, Vertex A_i and Vertex A_{i+1} are directly connected by an edge.

An empty sequence is regarded as a path of length 0.

Let S = s_1s_2\ldots s_N be a string of length N consisting of 0 and 1. A path A = (A_1, A_2, \ldots, A_k) is said to be a good path with respect to S if the following conditions are satisfied:

• For all i = 1, 2, \ldots, N, it holds that:
  • if s_i = 0, then A has even number of i's.
  • if s_i = 1, then A has odd number of i's.

There are 2^N possible S (in other words, there are 2^N strings of length N consisting of 0 and 1). Find the sum of "the length of the shortest good path with respect to S" over all those S.

Under the Constraints of this problem, it can be proved that, for any string S of length N consisting of 0 and 1, there is at least one good path with respect to S.

Constraints

• 2 \leq N \leq 17
• N-1 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq u_i, v_i \leq N
• The given graph is simple and connected.
• All values in input are integers.

Sample Input 1

3 2
1 2
2 3

Sample Output 1

14

• For S = 000, the empty sequence () is the shortest good path with respect to S, whose length is 0.
• For S = 100, (1) is the shortest good path with respect to S, whose length is 1.
• For S = 010, (2) is the shortest good path with respect to S, whose length is 1.
• For S = 110, (1, 2) is the shortest good path with respect to S, whose length is 2.
• For S = 001, (3) is the shortest good path with respect to S, whose length is 1.
• For S = 101, (1, 2, 3, 2) is the shortest good path with respect to S, whose length is 4.
• For S = 011, (2, 3) is the shortest good path with respect to S, whose length is 2.
• For S = 111, (1, 2, 3) is the shortest good path with respect to S, whose length is 3.

Therefore, the sought answer is 0 + 1 + 1 + 2 + 1 + 4 + 2 + 3 = 14.

Sample Input 2

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

Sample Output 2

108