Problem Statement

Takahashi is at the origin of a number line. He wants to reach a goal at coordinate X.

There is a wall at coordinate Y, which Takahashi cannot go beyond at first.
However, after picking up a hammer at coordinate Z, he can destroy that wall and pass through.

Determine whether Takahashi can reach the goal. If he can, find the minimum total distance he needs to travel to do so.

Constraints

• -1000 \leq X,Y,Z \leq 1000
• X, Y, and Z are distinct, and none of them is 0.
• All values in the input are integers.

Sample Input 1

10 -10 1

Sample Output 1

10

Takahashi can go straight to the goal.

Sample Input 2

20 10 -10

Sample Output 2

40

The goal is beyond the wall. He can get there by first picking up the hammer and then destroying the wall.

Sample Input 3

100 1 1000

Sample Output 3

-1

Problem Statement

You are given a string S. Find the maximum length of a contiguous substring of S that is a palindrome.
Note that there is always a contiguous substring of S that is a palindrome.

Constraints

• S is a string of length between 2 and 100, inclusive, consisting of uppercase English letters.

Sample Input 1

TOYOTA

Sample Output 1

5

TOYOT, a contiguous substring of TOYOTA, is a palindrome of length 5.
TOYOTA, the only length-6 contiguous substring of TOYOTA, is not a palindrome, so print 5.

Sample Input 2

ABCDEFG

Sample Output 2

1

Every contiguous substring of length 1 is a palindrome.

Sample Input 3

AAAAAAAAAA

Sample Output 3

10

Problem Statement

There are N people standing in a line: person 1, person 2, \ldots, person N.

You are given the arrangement of the people as a sequence A=(A _ 1,A _ 2,\ldots,A _ N) of length N.

A _ i\ (1\leq i\leq N) represents the following information:

• if A _ i=-1, person i is at the front of the line;
• if A _ i\neq -1, person i is right behind person A _ i.

Print the people's numbers in the line from front to back.

Constraints

• 1\leq N\leq3\times10 ^ 5
• A _ i=-1 or 1\leq A _ i\leq N\ (1\leq i\leq N)
• There is exactly one way to arrange the N people consistent with the information given.
• All input values are integers.

Sample Input 1

6
4 1 -1 5 3 2

Sample Output 1

3 5 4 1 2 6

If person 3, person 5, person 4, person 1, person 2, and person 6 stand in line in this order from front to back, the arrangement matches the given information.

Indeed, it can be seen that:

• person 1 is standing right behind person 4,
• person 2 is standing right behind person 1,
• person 3 is at the front of the line,
• person 4 is standing right behind person 5,
• person 5 is standing right behind person 3, and
• person 6 is standing right behind person 2.

Thus, print 3, 5, 4, 1, 2, and 6 in this order, separated by spaces.

Sample Input 2

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

Sample Output 2

1 2 3 4 5 6 7 8 9 10

Sample Input 3

30
3 25 20 6 18 12 26 1 29 -1 21 17 23 9 8 30 10 15 22 27 4 13 5 11 16 24 28 2 19 7

Sample Output 3

10 17 12 6 4 21 11 24 26 7 30 16 25 2 28 27 20 3 1 8 15 18 5 23 13 22 19 29 9 14

Problem Statement

The coordinate plane is covered with 2\times1 tiles. The tiles are laid out according to the following rules:

• For an integer pair (i,j), the square A _ {i,j}=\lbrace(x,y)\mid i\leq x\leq i+1\wedge j\leq y\leq j+1\rbrace is contained in one tile.
• When i+j is even, A _ {i,j} and A _ {i + 1,j} are contained in the same tile.

Tiles include their boundaries, and no two different tiles share a positive area.

Near the origin, the tiles are laid out as follows:

Takahashi starts at the point (S _ x+0.5,S _ y+0.5) on the coordinate plane.

He can repeat the following move as many times as he likes:

• Choose a direction (up, down, left, or right) and a positive integer n. Move n units in that direction.

Each time he enters a tile, he pays a toll of 1.

Find the minimum toll he must pay to reach the point (T _ x+0.5,T _ y+0.5).

Constraints

• 0\leq S _ x\leq2\times10 ^ {16}
• 0\leq S _ y\leq2\times10 ^ {16}
• 0\leq T _ x\leq2\times10 ^ {16}
• 0\leq T _ y\leq2\times10 ^ {16}
• All input values are integers.

Sample Input 1

5 0
2 5

Sample Output 1

5

For example, Takahashi can pay a toll of 5 by moving as follows:

• Move left by 1. Pay a toll of 0.
• Move up by 1. Pay a toll of 1.
• Move left by 1. Pay a toll of 0.
• Move up by 3. Pay a toll of 3.
• Move left by 1. Pay a toll of 0.
• Move up by 1. Pay a toll of 1.

It is impossible to reduce the toll to 4 or less, so print 5.

Sample Input 2

3 1
4 1

Sample Output 2

0

There are cases where no toll needs to be paid.

Sample Input 3

2552608206527595 5411232866732612
771856005518028 7206210729152763

Sample Output 3

1794977862420151

Note that the value to be output may exceed the range of a 32-bit integer.

Problem Statement

Takahashi will toss a coin N times. He also has a counter, which initially shows 0.

Depending on the result of the i-th coin toss, the following happens:

• If it heads: Takahashi increases the counter's value by 1 and receives X_i yen (Japanese currency).
• If it tails: he resets the counter's value to 0, without receiving money.

Additionally, there are M kinds of streak bonuses. The i-th kind of streak bonus awards Y_i yen each time the counter shows C_i.

Find the maximum amount of money that Takahashi can receive.

Constraints

• 1\leq M\leq N\leq 5000
• 1\leq X_i\leq 10^9
• 1\leq C_i\leq N
• 1\leq Y_i\leq 10^9
• C_1,C_2,\ldots,C_M are all different.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

48

If he gets head, head, tail, head, head, head, in this order, the following amounts of money are awarded.

• In the 1-st coin toss, the coin heads. Change the counter's value from 0 to 1 and receive 2 yen.
• In the 2-nd coin toss, the coin heads. Change the counter's value from 1 to 2 and receive 7 yen. Additionally, get 10 yen as a streak bonus.
• In the 3-rd coin toss, the coin tails. Change the counter's value from 2 to 0.
• In the 4-th coin toss, the coin heads. Change the counter's value from 0 to 1 and receive 8 yen.
• In the 5-th coin toss, the coin heads. Change the counter's value from 1 to 2 and receive 2 yen. Additionally, get 10 yen as a streak bonus.
• In the 6-th coin toss, the coin heads. Change the counter's value from 2 to 3 and receive 8 yen. Additionally, get 1 yen as a streak bonus.

In this case, Takahashi receives 2+(7+10)+0+8+(2+10)+(8+1)=48 yen in total, which is the maximum possible.
Note that streak bonuses are awarded any number of times each time the counter shows C_i.
As a side note, if he gets head in all 6 coin tosses, he only receives 2+(7+10)+(1+1)+8+(2+5)+8=44 yen, which is not the maximum.

Sample Input 2

3 2
1000000000 1000000000 1000000000
1 1000000000
3 1000000000

Sample Output 2

5000000000

Note that the answer may not fit into a 32-bit integer type.