Problem Statement

In AtCoder, a user's rating is given as a positive integer, and based on this value, a certain number of ^ is displayed. Specifically, when the rating is between 1 and 399, inclusive, the display rules are as follows:

• When the rating is between 1 and 99, inclusive, ^ is displayed once.
• When the rating is between 100 and 199, inclusive, ^ is displayed twice.
• When the rating is between 200 and 299, inclusive, ^ is displayed three times.
• When the rating is between 300 and 399, inclusive, ^ is displayed four times.

Currently, Takahashi's rating is R. Here, it is guaranteed that R is an integer between 1 and 299, inclusive.
Find the minimum increase in rating required for him to increase the number of displayed ^.
It can be proved that under the constraints of this problem, he can increase the number of ^ without raising his rating to 400 or above.

Constraints

• 1 \leq R \leq 299
• R is an integer.

Sample Input 1

123

Sample Output 1

77

Takahashi's current rating is 123, and ^ is displayed twice.
By increasing his rating by 77, his rating will become 200, and ^ will be displayed three times. When the rating is 199 or below, ^ is displayed not more than twice, so print 77.

Sample Input 2

250

Sample Output 2

50

Problem Statement

Keyence has a culture of addressing everyone with the honorific "san," regardless of their role, age, or position. Even a new employee would call the president "Nakata-san." [Translator's note: this is a bit unusual in Japan.]

You are given a person's surname and first name as strings S and T, respectively.

Print the concatenation of the surname, a space ( ), and the honorific (san) in this order.

Constraints

• Each of S and T is a string that satisfies the following conditions.
  • The length is between 1 and 10, inclusive.
  • The first character is an uppercase English letter.
  • All characters except the first one are lowercase English letters.

Sample Input 1

Takahashi Chokudai

Sample Output 1

Takahashi san

Print the concatenation of the surname (Takahashi), a space ( ), and the honorific (san) in this order.

Sample Input 2

K Eyence

Sample Output 2

K san

Problem Statement

You are given a string S of length N consisting of lowercase English letters. The x-th (1 \le x \le N) character of S is S_x.

For each i=1,2,\dots,N-1, find the maximum non-negative integer l that satisfies all of the following conditions:

• l+i \le N, and
• for all integers k such that 1 \le k \le l, it holds that S_{k} \neq S_{k+i}.

Note that l=0 always satisfies the conditions.

Constraints

• N is an integer such that 2 \le N \le 5000.
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

6
abcbac

Sample Output 1

5
1
2
0
1

In this input, S= abcbac.

• When i=1, we have S_1 \neq S_2, S_2 \neq S_3, \dots, and S_5 \neq S_6, so the maximum value is l=5.
• When i=2, we have S_1 \neq S_3 but S_2 = S_4, so the maximum value is l=1.
• When i=3, we have S_1 \neq S_4 and S_2 \neq S_5 but S_3 = S_6, so the maximum value is l=2.
• When i=4, we have S_1 = S_5, so the maximum value is l=0.
• When i=5, we have S_1 \neq S_6, so the maximum value is l=1.

Problem Statement

There are N people numbered 1 to N.

Person i guessed the building area of KEYENCE headquarters building to be S_i square meters.

The shape of KEYENCE headquarters building is shown below, where a and b are some positive integers.
That is, the building area of the building can be represented as 4ab+3a+3b.

Based on just this information, how many of the N people are guaranteed to be wrong in their guesses?

Constraints

• 1 \leq N \leq 20
• 1 \leq S_i \leq 1000
• All values in input are integers.

Sample Input 1

3
10 20 39

Sample Output 1

1

The area would be 10 square meters if a=1,b=1, and 39 square meters if a=2,b=3.

However, no pair of positive integers a and b would make the area 20 square meters.

Thus, we can only be sure that Person 2 guessed wrong.

Sample Input 2

5
666 777 888 777 666

Sample Output 2

3

Problem Statement

Takahashi is going to read a manga series "Snuke-kun" in 10^9 volumes.
Initially, Takahashi has N books of this series. The i-th book is Volume a_i.

Takahashi may repeat the following operation any number of (possibly zero) times only before he begins to read:

• Do nothing if he has 1 or less books; otherwise, sell two of the books he has and buy one book of any volume instead.

Then, Takahashi reads Volume 1, Volume 2, Volume 3, \ldots, in order. However, when he does not have a book of the next volume to read, he stops reading the series (regardless of the other volumes he has).

Find the latest volume of the series that he can read up to. If he cannot read any, let the answer be 0.

Constraints

• 1 \leq N \leq 3 \times 10^5
• 1 \leq a_i \leq 10^9
• All values in the input are integers.

Sample Input 1

6
1 2 4 6 7 271

Sample Output 1

4

Before he begins to read the series, he may do the following operation: "sell books of Volumes 7 and 271 and buy one book of Volume 3 instead." Then, he has one book each of Volumes 1, 2, 3, 4, and 6.
If he then begins to read the series, he reads Volumes 1, 2, 3, and 4, then tries to read Volume 5. However, he does not have one, so he stops reading at this point.
Regardless of the choices in the operation, he cannot read Volume 5, so the answer is 4.

Sample Input 2

10
1 1 1 1 1 1 1 1 1 1

Sample Output 2

5

Takahashi may have multiple books of the same volume.
For this input, if he performs the following 4 operations before he begins to read the series, he can read up to Volume 5, which is the maximum:

• Sell two books of Volume 1 and buy a book of Volume 2 instead.
• Sell two books of Volume 1 and buy a book of Volume 3 instead.
• Sell two books of Volume 1 and buy a book of Volume 4 instead.
• Sell two books of Volume 1 and buy a book of Volume 5 instead.

Sample Input 3

1
5

Sample Output 3

0

Takahashi cannot read Volume 1.

Problem Statement

Takahashi is on a two-dimensional plane. Starting from the origin, he made N moves.

The N moves are represented by a string of length N as described below:

• Takahashi's coordinates after the i-th move are:

  • (x+1,y) if the i-th character of S is R;
  • (x-1,y) if the i-th character of S is L;
  • (x,y+1) if the i-th character of S is U; and
  • (x,y-1) if the i-th character of S is D,

  where (x,y) is his coordinates before the move.

Determine if Takahashi visited the same coordinates multiple times in the course of the N moves (including the starting and ending points).

Constraints

• 1 \leq N \leq 2\times 10^5
• N is an integer.
• S is a string of length N consisting of R, L, U, and D.

Sample Input 1

5
RLURU

Sample Output 1

Yes

Takahashi's coordinates change as follows: (0,0)\to (1,0)\to (0,0)\to (0,1)\to (1,1)\to (1,2).

Sample Input 2

20
URDDLLUUURRRDDDDLLLL

Sample Output 2

No

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

For a sequence X, let f(X) = (the minimum number of elements one must modify to make X a palindrome).

Given a sequence A of length N, find the sum of f(X) over all contiguous subarrays of A.

Here, a sequence X of length m is said to be a palindrome if and only if the i-th and the (m+1-i)-th elements of X are equal for all 1 \le i \le m.

Constraints

• All values in the input are integers.
• 1 \le N \le 2 \times 10^5
• 1 \le A_i \le N

Sample Input 1

5
5 2 1 2 2

Sample Output 1

9

• f(5) = 0
• f(2) = 0
• f(1) = 0
• f(2) = 0
• f(2) = 0
• f(5,2) = 1
• f(2,1) = 1
• f(1,2) = 1
• f(2,2) = 0
• f(5,2,1) = 1
• f(2,1,2) = 0
• f(1,2,2) = 1
• f(5,2,1,2) = 2
• f(2,1,2,2) = 1
• f(5,2,1,2,2) = 1

Therefore, the sought answer is 9.

Problem Statement

There are N Christmas trees on a two-dimensional plane. The i-th (1\le i\le N) Christmas tree is located at coordinates (X_i,Y_i).

You are given Q queries. Process the queries in order. Each query is one of the following:

• Type 1 : Given in the form 1 i x y. Change the coordinates of the i-th Christmas tree to (x,y).
• Type 2 : Given in the form 2 L R x y. Output the Manhattan distance from the coordinates (x,y) to the farthest Christmas tree among the L,L+1,\ldots,R-th Christmas trees.

Here, the Manhattan distance between coordinates (x_1,y_1) and coordinates (x_2,y_2) is defined as |x_1-x_2|+|y_1-y_2|.

Constraints

• 1\le N,Q\le 2\times 10^5
• -10^9\le X_i,Y_i\le 10^9
• 1\le i\le N
• 1\le L\le R\le N
• -10^9\le x,y\le 10^9
• All input values are integers.

Sample Input 1

3 4
-1 -1
1 2
-2 1
2 1 2 0 0
2 1 3 -1 2
1 1 0 1
2 1 3 -1 2

Sample Output 1

3
3
2

Initially, the 1st, 2nd, 3rd Christmas trees are located at coordinates (-1,-1), (1,2), (-2,1), respectively.

Each query is processed as follows:

• The Manhattan distances from the 1st and 2nd Christmas trees to coordinates (0,0) are 2 and 3, respectively. Thus, output 3, which is the maximum value among 2,3.
• The Manhattan distances from the 1st, 2nd, 3rd Christmas trees to coordinates (-1,2) are 3, 2, 2, respectively. Thus, output 3, which is the maximum value among 3,2,2.
• Change the coordinates of the 1st Christmas tree to (0,1). The coordinates of the 1st, 2nd, 3rd Christmas trees become (0,1),(1,2),(-2,1), respectively.
• The Manhattan distances from the 1st, 2nd, 3rd Christmas trees to coordinates (-1,2) are 2, 2, 2, respectively. Thus, output 2, which is the maximum value among 2,2,2.

Sample Input 2

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

Sample Output 2

24
24
22
30
9