Problem Statement

There is 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.

If S_{i,j} is #, the cell (i,j) is impassable; if it is ., the cell is passable and contains no house; if it is @, the cell is passable and contains a house.

Initially, Santa Claus is in cell (X,Y). He will act according to the string T as follows.

• Let |T| be the length of the string T. For i=1,2,\ldots,|T|, he moves as follows.
  • Let (x,y) be the cell he is currently in.
    • If T_i is U and cell (x-1,y) is passable, move to cell (x-1,y).
    • If T_i is D and cell (x+1,y) is passable, move to cell (x+1,y).
    • If T_i is L and cell (x,y-1) is passable, move to cell (x,y-1).
    • If T_i is R and cell (x,y+1) is passable, move to cell (x,y+1).
    • Otherwise, stay in cell (x,y).

Find the cell where he is after completing all actions, and the number of distinct houses that he passed through or arrived at during his actions. If the same house is passed multiple times, it is only counted once.

Constraints

• 3 \leq H,W \leq 100
• 1 \leq X \leq H
• 1 \leq Y \leq W
• All given numbers are integers.
• Each S_{i,j} is one of #, ., @.
• S_{i,1} and S_{i,W} are # for every 1 \leq i \leq H.
• S_{1,j} and S_{H,j} are # for every 1 \leq j \leq W.
• S_{X,Y}= .
• T is a string of length at least 1 and at most 10^4, consisting of U, D, L, R.

Sample Input 1

5 5 3 4
#####
#...#
#.@.#
#..@#
#####
LLLDRUU

Sample Output 1

2 3 1

Santa Claus behaves as follows:

• T_1= L, so he moves from (3,4) to (3,3). A house is passed.
• T_2= L, so he moves from (3,3) to (3,2).
• T_3= L, but cell (3,1) is impassable, so he stays at (3,2).
• T_4= D, so he moves from (3,2) to (4,2).
• T_5= R, so he moves from (4,2) to (4,3).
• T_6= U, so he moves from (4,3) to (3,3). A house is passed, but it has already been passed.
• T_7= U, so he moves from (3,3) to (2,3).

The number of houses he passed or arrived during his actions is 1.

Sample Input 2

6 13 4 6
#############
#@@@@@@@@@@@#
#@@@@@@@@@@@#
#@@@@.@@@@@@#
#@@@@@@@@@@@#
#############
UURUURLRLUUDDURDURRR

Sample Output 2

3 11 11

Sample Input 3

12 35 7 10
###################################
#.................................#
#..........@......................#
#......@................@.........#
#.............##............@.....#
#...##........##....##............#
#...##........##....##.......##...#
#....##......##......##....##.....#
#....##......##......##..##.......#
#.....#######.........###.........#
#.................................#
###################################
LRURRRUUDDULUDUUDLRLRDRRLULRRUDLDRU

Sample Output 3

4 14 1

Problem Statement

There is a keyboard with 26 keys arranged on a number line.

The arrangement of this keyboard is represented by a string S, which is a permutation of ABCDEFGHIJKLMNOPQRSTUVWXYZ. The key corresponding to the character S_x is located at coordinate x (1 \leq x \leq 26). Here, S_x denotes the x-th character of S.

You will use this keyboard to input ABCDEFGHIJKLMNOPQRSTUVWXYZ in this order, typing each letter exactly once with your right index finger. To input a character, you need to move your finger to the coordinate of the key corresponding to that character and press the key.

Initially, your finger is at the coordinate of the key corresponding to A. Find the minimal possible total traveled distance of your finger from pressing the key for A to pressing the key for Z. Here, pressing a key does not contribute to the distance.

Constraints

• S is a permutation of ABCDEFGHIJKLMNOPQRSTUVWXYZ.

Sample Input 1

ABCDEFGHIJKLMNOPQRSTUVWXYZ

Sample Output 1

25

From pressing the key for A to pressing the key for Z, you need to move your finger 1 unit at a time in the positive direction, resulting in a total traveled distance of 25. It is impossible to press all keys with a total traveled distance less than 25, so print 25.

Sample Input 2

MGJYIZDKSBHPVENFLQURTCWOAX

Sample Output 2

223

Problem Statement

You are given a sequence of N positive integers A=(A_1,A_2,\dots,A_N).

Find the number of pairs of integers (l,r) satisfying 1\leq l\leq r\leq N such that the subsequence (A_l,A_{l+1},\dots,A_r) forms an arithmetic progression.

A sequence (x_1,x_2,\dots,x_{|x|}) is an arithmetic progression if and only if there exists a d such that x_{i+1}-x_i=d\ (1\leq i < |x|). In particular, a sequence of length 1 is always an arithmetic progression.

Constraints

• 1\leq N \leq 2\times 10^5
• 1\leq A_i \leq 10^9
• All input values are integers.

Sample Input 1

4
3 6 9 3

Sample Output 1

8

There are eight pairs of integers (l,r) satisfying the condition: (1,1),(2,2),(3,3),(4,4),(1,2),(2,3),(3,4),(1,3).

Indeed, when (l,r)=(1,3), (A_l,\dots,A_r)=(3,6,9) is an arithmetic progression, so it satisfies the condition. However, when (l,r)=(2,4), (A_l,\dots,A_r)=(6,9,3) is not an arithmetic progression, so it does not satisfy the condition.

Sample Input 2

5
1 1 1 1 1

Sample Output 2

15

All pairs of integers (l,r)\ (1\leq l\leq r\leq 5) satisfy the condition.

Sample Input 3

8
87 42 64 86 72 58 44 30

Sample Output 3

22

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

Takahashi is trying to catch many Snuke.

There are five pits at coordinates 0, 1, 2, 3, and 4 on a number line, connected to Snuke's nest.

Now, N Snuke will appear from the pits. It is known that the i-th Snuke will appear from the pit at coordinate X_i at time T_i, and its size is A_i.

Takahashi is at coordinate 0 at time 0 and can move on the line at a speed of at most 1.
He can catch a Snuke appearing from a pit if and only if he is at the coordinate of that pit exactly when it appears.
The time it takes to catch a Snuke is negligible.

Find the maximum sum of the sizes of Snuke that Takahashi can catch by moving optimally.

Constraints

• 1 \leq N \leq 10^5
• 0 < T_1 < T_2 < \ldots < T_N \leq 10^5
• 0 \leq X_i \leq 4
• 1 \leq A_i \leq 10^9
• All values in input are integers.

Sample Input 1

3
1 0 100
3 3 10
5 4 1

Sample Output 1

101

The optimal strategy is as follows.

• Wait at coordinate 0 to catch the first Snuke at time 1.
• Go to coordinate 4 to catch the third Snuke at time 5.

It is impossible to catch both the first and second Snuke, so this is the best he can.

Sample Input 2

3
1 4 1
2 4 1
3 4 1

Sample Output 2

0

Takahashi cannot catch any Snuke.

Sample Input 3

10
1 4 602436426
2 1 623690081
3 3 262703497
4 4 628894325
5 3 450968417
6 1 161735902
7 1 707723857
8 2 802329211
9 0 317063340
10 2 125660016

Sample Output 3

2978279323