Problem Statement

You are given a 3-character string S, which is a concatenation of integers a and b between 1 and 9 (inclusive) and the character x in this order: axb.

Find the product of a and b.

Constraints

• The length of S is 3.
• The 1-st and 3-rd characters are digits between 1 and 9 (inclusive).
• The 2-nd character is x.

Sample Input 1

3x7

Sample Output 1

21

We have 3 \times 7 = 21, which should be printed.

Sample Input 2

9x9

Sample Output 2

81

Sample Input 3

1x1

Sample Output 3

1

Problem Statement

Print all non-negative integers less than or equal to N in descending order.

Constraints

• 1 \leq N \leq 100
• N is an integer.

Sample Input 1

3

Sample Output 1

3
2
1
0

We have four non-negative integers less than or equal to 3, which are 0, 1, 2, and 3.
To print them in descending order, print 3 in the first line, 2 in the second, 1 in the third, and 0 in the fourth.

Sample Input 2

22

Sample Output 2

22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0

Problem Statement

N examinees took an entrance exam.
The examinee numbered i scored A_i points in math and B_i points in English.

The admissions are determined as follows.

1. X examinees with the highest math scores are admitted.
2. Then, among the examinees who are not admitted yet, Y examinees with the highest English scores are admitted.
3. Then, among the examinees who are not admitted yet, Z examinees with the highest total scores in math and English are admitted.
4. Those examinees who are not admitted yet are rejected.

Here, in each of the steps 1. to 3., ties are broken by examinees' numbers: an examinee with the smaller examinee's number is prioritized. See also Sample Input and Output.

Print the examinees' numbers of the admitted examinees determined by the steps above in ascending order, separated by newlines.

Constraints

• All values in input are integers.
• 1 \le N \le 1000
• 0 \le X,Y,Z \le N
• 1 \le X+Y+Z \le N
• 0 \le A_i,B_i \le 100

Sample Input 1

6 1 0 2
80 60 80 60 70 70
40 20 50 90 90 80

Sample Output 1

1
4
5

• First, 1 examinee with the highest math score is admitted.
  • Examinee 1 is tied with Examinee 3, scoring the highest 80 points in math, and the tie is broken by the examinees' numbers, so Examinee 1 is admitted.
• Then, among the examinees who are not admitted yet, 0 examinees with the highest English scores are admitted.
  • Obviously, it does not affect the admissions.
• Then, among the examinees who are not admitted yet, 2 examinees with the highest total scores in math and English are admitted.
  • First, among the examinees who are not admitted yet, Examinee 5 is admitted, scoring the highest total score of 160 points.
  • Next, among the examinees who are not admitted yet, Examinee 4 is tied with Examinee 6, scoring a total score of 150 points. The tie is broken by the examinees' numbers, and Examinee 4 is admitted.

Therefore, the examinees' numbers of the admitted examinees are 1, 4, and 5. Print them in ascending order.

Sample Input 2

5 2 1 2
0 100 0 100 0
0 0 100 100 0

Sample Output 2

1
2
3
4
5

All examinees may be admitted.

Sample Input 3

15 4 3 2
30 65 20 95 100 45 70 85 20 35 95 50 40 15 85
0 25 45 35 65 70 80 90 40 55 20 20 45 75 100

Sample Output 3

2
4
5
6
7
8
11
14
15

Problem Statement

Bowling pins are numbered 1 through 10. The following figure is a top view of the arrangement of the pins:

Let us call each part between two dotted lines in the figure a column.
For example, Pins 1 and 5 belong to the same column, and so do Pin 3 and 9.

When some of the pins are knocked down, a special situation called split may occur.
A placement of the pins is a split if both of the following conditions are satisfied:

• Pin 1 is knocked down.
• There are two different columns that satisfy both of the following conditions:
  • Each of the columns has one or more standing pins.
  • There exists a column between these columns such that all pins in the column are knocked down.

See also Sample Inputs and Outputs for examples.

Now, you are given a placement of the pins as a string S of length 10. For i = 1, \dots, 10, the i-th character of S is 0 if Pin i is knocked down, and is 1 if it is standing.
Determine if the placement of the pins represented by S is a split.

Constraints

• S is a string of length 10 consisting of 0 and 1.

Sample Input 1

0101110101

Sample Output 1

Yes

In the figure below, the knocked-down pins are painted gray, and the standing pins are painted white:

Between the column containing a standing pin 5 and the column containing a standing pin 6 is a column containing Pins 3 and 9. Since Pins 3 and 9 are both knocked down, the placement is a split.

Sample Input 2

0100101001

Sample Output 2

Yes

Sample Input 3

0000100110

Sample Output 3

No

This placement is not a split.

Sample Input 4

1101110101

Sample Output 4

No

This is not a split because Pin 1 is not knocked down.

Problem Statement

There is a grid with H rows and W columns.

Each cell of the grid is land or sea, which is represented by H strings S_1, S_2, \ldots, S_H of length W. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left, and (i, j) is land if the j-th character of S_i is ., and (i, j) is sea if the character is #.

The constraints guarantee that all cells on the perimeter of the grid (that is, the cells (i, j) that satisfy at least one of i = 1, i = H, j = 1, j = W) are sea.

Takahashi's spaceship has crash-landed on a cell in the grid. Afterward, he moved N times on the grid following the instructions represented by a string T of length N consisting of L, R, U, and D. For i = 1, 2, \ldots, N, the i-th character of T describes the i-th move as follows:

• L indicates a move of one cell to the left. That is, if he is at (i, j) before the move, he will be at (i, j-1) after the move.
• R indicates a move of one cell to the right. That is, if he is at (i, j) before the move, he will be at (i, j+1) after the move.
• U indicates a move of one cell up. That is, if he is at (i, j) before the move, he will be at (i-1, j) after the move.
• D indicates a move of one cell down. That is, if he is at (i, j) before the move, he will be at (i+1, j) after the move.

It is known that all cells along his path (including the cell where he crash-landed and the cell he is currently on) are not sea. Print the number of cells that could be his current position.

Constraints

• H, W, and N are integers.
• 3 \leq H, W \leq 500
• 1 \leq N \leq 500
• T is a string of length N consisting of L, R, U, and D.
• S_i is a string of length W consisting of . and #.
• There is at least one cell that could be Takahashi's current position.
• All cells on the perimeter of the grid are sea.

Sample Input 1

6 7 5
LULDR
#######
#...#.#
##...##
#.#...#
#...#.#
#######

Sample Output 1

2

The following two cases are possible, so there are two cells that could be Takahashi's current position: (3, 4) and (4, 5).

• He crash-landed on cell (3, 5) and moved (3, 5) \rightarrow (3, 4) \rightarrow (2, 4) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 4).
• He crash-landed on cell (4, 6) and moved (4, 6) \rightarrow (4, 5) \rightarrow (3, 5) \rightarrow (3, 4) \rightarrow (4, 4) \rightarrow (4, 5).

Sample Input 2

13 16 9
ULURDLURD
################
##..##.#..####.#
###.#..#.....#.#
#..##..#####.###
#...#..#......##
###.##.#..#....#
##.#####....##.#
###.###.#.#.#..#
######.....##..#
#...#.#.######.#
##..###..#..#.##
#...#.#.#...#..#
################

Sample Output 2

6