Problem Statement

You have a bankbook from The Terrifying Bank. The deposit passbook of the bank has a terrifyingly scary property that the commission fee changes according to the withdrawal amount.

To withdraw money from the passbook, you need to specify the withdrawal amount in units of 1\,000 yen, and pay a commission fee of C yen per 1\,000 yen of withdrawal amount separately from the balance. Withdrawals are not allowed if they would leave the balance below 0 yen.

When the balance of your passbook from the bank is X yen, what is the maximum amount of money you can withdraw from it?

Constraints

• 1 \leq X \leq 10^7
• 1 \leq C \leq 999
• All input values are integers.

Sample Input 1

650000 8

Sample Output 1

644000

The commission fee required to withdraw 644\,000 yen is 644\,000 \times \displaystyle\frac{8}{1000} = 5\,152 yen, so since 644\,000 + 5\,152 \leq 650\,000, you can withdraw 644\,000 yen.

On the other hand, the commission fee required to withdraw 645\,000 yen is 645\,000 \times \displaystyle\frac{8}{1000} = 5\,160 yen, so since 645\,000 + 5\,160 > 650\,000, you cannot withdraw 645\,000 yen.

Sample Input 2

1003 4

Sample Output 2

0

It is possible that no money can be withdrawn at all.

Sample Input 3

10000000 24

Sample Output 3

9765000

Problem Statement

Team Takahashi and Team Aoki played N matches. In the i-th match (1\leq i\leq N), Team Takahashi scored X _ i points, and Team Aoki scored Y _ i points.

The team with the higher total score from the N matches wins.

Print the winner. If the two teams have the same total score, it is a draw.

Constraints

• 1\leq N\leq 100
• 0\leq X _ i\leq 100\ (1\leq i\leq N)
• 0\leq Y _ i\leq 100\ (1\leq i\leq N)
• All input values are integers.

Sample Input 1

4
10 2
10 1
10 2
3 2

Sample Output 1

Takahashi

In four matches, Team Takahashi scored 33 points, and Team Aoki scored 7 points. Team Takahashi wins, so print Takahashi.

Sample Input 2

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

Sample Output 2

Draw

Both teams scored 22 points. It is a draw, so print Draw.

Sample Input 3

4
0 0
10 10
50 50
0 100

Sample Output 3

Aoki

One or both teams may score no points in a match.

Problem Statement

Given a non-negative integer X, perform the following operation for i=1,2,\dots,K in this order and find the resulting X.

• Round X off to the nearest 10^i.
  • Formally, replace X with Y that is "the largest multiple of 10^i that minimizes |Y-X|."
  • Here are some examples:
    • Rounding 273 off to the nearest 10^2 yields 300.
    • Rounding 999 off to the nearest 10^3 yields 1000.
    • Rounding 100 off to the nearest 10^{10} yields 0.
    • Rounding 1015 off to the nearest 10^1 yields 1020.

Constraints

• X and K are integers.
• 0 \le X < 10^{15}
• 1 \le K \le 15

Sample Input 1

2048 2

Sample Output 1

2100

X changes as 2048 \rightarrow 2050 \rightarrow 2100 by the operations.

Sample Input 2

1 15

Sample Output 2

0

Sample Input 3

999 3

Sample Output 3

1000

Sample Input 4

314159265358979 12

Sample Output 4

314000000000000

X may not fit into a 32-bit integer type.

Problem Statement

There are N points in a two-dimensional plane. The coordinates of the i-th point are (x_i,y_i).

Find the maximum length of a segment connecting two of these points.

Constraints

• 2 \leq N \leq 100
• -1000 \leq x_i,y_i \leq 1000
• (x_i,y_i) \neq (x_j,y_j)\ (i \neq j)
• All values in input are integers.

Sample Input 1

3
0 0
0 1
1 1

Sample Output 1

1.4142135624

For the 1-st and 3-rd points, the length of the segment connecting them is \sqrt 2 = 1.41421356237\dots, which is the maximum length.

Sample Input 2

5
315 271
-2 -621
-205 -511
-952 482
165 463

Sample Output 2

1455.7159750446

Problem Statement

There are N gems. The color (represented as an integer) of the i-th gem is C_i and its value is V_i.

Choose K gems from these N gems. Here, the chosen gems must have at least M distinct colors.

Find the maximum possible total value of the chosen gems. (Such a choice is always possible in the given input.)

Constraints

• 1 \leq M \leq K \leq N \leq 2 \times 10^5
• 1 \leq C_i \leq N
• 1 \leq V_i \leq 10^9
• There exist gems of at least M distinct colors.
• All input values are integers.

Sample Input 1

5 3 2
1 30
1 40
1 50
2 10
3 20

Sample Output 1

110

In this sample, choose three gems from five gems. The chosen gems must have at least two distinct colors.

Choosing gems 2, 3, 5 gives colors 1, 1, 3, which are two distinct colors. Their total value is 40 + 50 + 20 = 110, and this is the maximum possible value.

Sample Input 2

5 3 3
1 30
1 40
1 50
2 10
3 20

Sample Output 2

80

The gems and the number to choose are the same as in Sample Input 1, but the chosen gems must have at least three distinct colors.

Choosing gems 3, 4, 5 gives colors 1, 2, 3, which are three distinct colors. Their total value is 50 + 10 + 20 = 80, and this is the maximum possible value.

Sample Input 3

5 5 1
4 1000000000
5 1000000000
4 1000000000
5 1000000000
4 1000000000

Sample Output 3

5000000000

Beware of overflow.

Problem Statement

There are N stations on a certain line operated by AtCoder Railway. The i-th station (1 \leq i \leq N) from the starting station is named S_i.

Local trains stop at all stations, while express trains may not. Specifically, express trains stop at only M \, (M \leq N) stations, and the j-th stop (1 \leq j \leq M) is the station named T_j.
Here, it is guaranteed that T_1 = S_1 and T_M = S_N, that is, express trains stop at both starting and terminal stations.

For each of the N stations, determine whether express trains stop at that station.

Constrains

• 2 \leq M \leq N \leq 10^5
• N and M are integers.
• S_i (1 \leq i \leq N) is a string of length between 1 and 10 (inclusive) consisting of lowercase English letters.
• S_i \neq S_j \, (i \neq j)
• T_1 = S_1 and T_M = S_N.
• (T_1, \dots, T_M) is obtained by removing zero or more strings from (S_1, \dots, S_N) and lining up the remaining strings without changing the order.

Sample Input 1

5 3
tokyo kanda akiba okachi ueno
tokyo akiba ueno

Sample Output 1

Yes
No
Yes
No
Yes

Sample Input 2

7 7
a t c o d e r
a t c o d e r

Sample Output 2

Yes
Yes
Yes
Yes
Yes
Yes
Yes

Express trains may stop at all stations.

Problem Statement

One day, Takahashi visited a cinema and decided to draw arrows on every floor tile, each pointing toward the nearest emergency exit.

You are given a grid with H rows and W columns. Let (i, j) denote the cell at the i-th row from the top and the j-th column from the left.
Each cell is represented by one of the following characters S_{i,j}:

• . : corridor cell
• # : wall cell
• E : emergency exit

For any corridor cell (i, j), define d(i, j), the distance to the nearest emergency exit, as follows:

• Starting from (i, j), repeatedly move to an adjacent non-wall cell in one of the four cardinal directions (up, down, left, right) until you reach an emergency exit. d(i, j) is the minimum number of moves required.

It is guaranteed that d(i, j) is definable for every corridor cell in the given grid; that is, every corridor cell (i, j) has at least one emergency exit reachable by passing through only corridor cells.

Write exactly one arrow (up, down, left, or right) in every corridor cell so that the following condition holds:

• For every corridor cell (i, j), if you start at (i, j) and perform the following action d(i, j) times, you reach an emergency exit:
  • Move one cell in the direction of the arrow written in your current cell. (You cannot move into a wall cell or outside the grid.)

Constraints

• 2 \le H \le 1000
• 2 \le W \le 1000
• Each S_{i,j} is ., #, or E.
• Every corridor cell (i, j) has at least one reachable emergency exit.
• H and W are integers.

Sample Input 1

3 4
...E
.#..
....

Sample Output 1

>>>E
^#>^
>>>^

Let us verify the condition for (2, 3) in the sample output. The distance from (2, 3) to the nearest emergency exit is 2, and following the arrows written in the sample output leads to an emergency exit in two moves.
The condition can be verified for every other corridor cell as well.

Sample Input 2

3 2
##
##
##

Sample Output 2

##
##
##

There may be cases with no corridor cells or emergency exits.

Sample Input 3

7 20
....................
..#..#..####..#E##..
..#..#..#..#..#.....
..E###..#..#..####..
.....#..#..E.....#..
.....#..####..####..
....................

Sample Output 3

>v<<<<<>>>>>>>>v<<<<
>v#^<#^^####v^#E##vv
>v#^<#v^#>v#vv#^<<<<
>>E###vv#>v#vv####^<
>>^<<#vv#>>E<<<<<#^<
>>^<<#vv####^<####^<
>>^<<<<<>>>>^<<<<<^<

Problem Statement

You are given integers N, M and three integer sequences of length M: X = (X_1, X_2, \ldots, X_M), Y = (Y_1, Y_2, \ldots, Y_M), and Z = (Z_1, Z_2, \ldots, Z_M). It is guaranteed that all elements of X and Y are between 1 and N, inclusive.

We call a length-N sequence of non-negative integers A = (A_1, A_2, \ldots, A_N) a good sequence if and only if it satisfies the following condition:

• For every integer i with 1 \le i \le M, the XOR of A_{X_i} and A_{Y_i} is Z_i.

Determine whether a good sequence A=(A_1,A_2,\ldots,A_N) exists, and if it exists, find one good sequence that minimizes the sum of its elements \displaystyle \sum_{i=1}^N A_i.

Constraints

• 1 \le N \le 2\times 10^5
• 0 \le M \le 10^5
• 1 \le X_i, Y_i \le N
• 0 \le Z_i \le 10^9
• All input values are integers.

Sample Input 1

3 2
1 3 4
1 2 3

Sample Output 1

0 3 4

A=(0,3,4) is a good sequence because A_1 \oplus A_2 = 3 and A_1 \oplus A_3 = 4.

Other good sequences include A=(1,2,5) and A=(7,4,3), but A=(0,3,4) has the smallest sum among all good sequences.

Sample Input 2

3 3
1 3 4
1 2 3
2 3 5

Sample Output 2

-1

No good sequence exists, so print -1.

Sample Input 3

5 8
4 2 4
2 3 11
3 4 15
4 5 6
3 2 11
3 3 0
3 1 9
3 4 15

Sample Output 3

0 2 9 6 0

Problem Statement

You are given length-N sequences of positive integers A=(A_1,A_2,\dots,A_N) and B=(B_1,B_2,\dots,B_N).
You are given Q queries.
Each query is of one of the following two types.

• 1 i x : Change A_i to x.
• 2 i x : Change B_i to x.

After processing each query, solve the following problem.

Takahashi needs to send an email to each of N companies and receive a reply from each of them.
Writing the email to send to the j-th company takes A_j minutes, and the reply arrives B_j minutes after it is sent.
He starts writing emails at time 0.
He can write the N emails in any order he likes, but he cannot write two or more emails simultaneously.
Find the minimum possible time at which he finishes receiving all of the replies.
Assume that the time taken to send emails is negligible.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• 1 \leq A_j,B_j \leq 10^9
• In each query, 1 \leq i \leq N.
• In each query, 1 \leq x \leq 10^9.
• All input values are integers.

Sample Input 1

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

Sample Output 1

16
16
13

After processing the first query, A=(4,1,7) and B=(4,6,7).
If Takahashi starts writing the email to send to company 3 at time 0, finishes writing it at time 7, and sends it to company 3, he receives the reply at time 14.
If he starts writing the email to send to company 2 at time 7, finishes writing it at time 8, and sends it to company 2, he receives the reply at time 14.
If he starts writing the email to send to company 1 at time 8, finishes writing it at time 12, and sends it to company 1, he receives the reply at time 16.