Problem Statement

You are given a trapezoid. The lengths of its upper base, lower base, and height are a, b, and h, respectively.

An example of a trapezoid

Find the area of this trapezoid.

Constraints

• 1≦a≦100
• 1≦b≦100
• 1≦h≦100
• All input values are integers.
• h is even.

Sample Input 1

3
4
2

Sample Output 1

7

When the lengths of the upper base, lower base, and height are 3, 4, and 2, respectively, the area of the trapezoid is (3+4)×2/2 = 7.

Sample Input 2

4
4
4

Sample Output 2

16

In this case, a parallelogram is given, which is also a trapezoid.

Problem Statement

Alice, Bob and Charlie are playing Card Game for Three, as below:

• At first, each of the three players has a deck consisting of some number of cards. Each card has a letter a, b or c written on it. The orders of the cards in the decks cannot be rearranged.
• The players take turns. Alice goes first.
• If the current player's deck contains at least one card, discard the top card in the deck. Then, the player whose name begins with the letter on the discarded card, takes the next turn. (For example, if the card says a, Alice takes the next turn.)
• If the current player's deck is empty, the game ends and the current player wins the game.

You are given the initial decks of the players. More specifically, you are given three strings S_A, S_B and S_C. The i-th (1≦i≦|S_A|) letter in S_A is the letter on the i-th card in Alice's initial deck. S_B and S_C describes Bob's and Charlie's initial decks in the same way.

Determine the winner of the game.

Constraints

• 1≦|S_A|≦100
• 1≦|S_B|≦100
• 1≦|S_C|≦100
• Each letter in S_A, S_B, S_C is a, b or c.

Sample Input 1

aca
accc
ca

Sample Output 1

A

The game will progress as below:

• Alice discards the top card in her deck, a. Alice takes the next turn.
• Alice discards the top card in her deck, c. Charlie takes the next turn.
• Charlie discards the top card in his deck, c. Charlie takes the next turn.
• Charlie discards the top card in his deck, a. Alice takes the next turn.
• Alice discards the top card in her deck, a. Alice takes the next turn.
• Alice's deck is empty. The game ends and Alice wins the game.

Sample Input 2

abcb
aacb
bccc

Sample Output 2

C

Problem Statement

You are given a string S consisting of digits between 1 and 9, inclusive. You can insert the letter + into some of the positions (possibly none) between two letters in this string. Here, + must not occur consecutively after insertion.

All strings that can be obtained in this way can be evaluated as formulas.

Evaluate all possible formulas, and print the sum of the results.

Constraints

• 1 \leq |S| \leq 10
• All letters in S are digits between 1 and 9, inclusive.

Sample Input 1

125

Sample Output 1

176

There are 4 formulas that can be obtained: 125, 1+25, 12+5 and 1+2+5. When each formula is evaluated,

• 125
• 1+25=26
• 12+5=17
• 1+2+5=8

Thus, the sum is 125+26+17+8=176.

Sample Input 2

9999999999

Sample Output 2

12656242944

Problem Statement

We have a grid with H rows and W columns. At first, all cells were painted white.

Snuke painted N of these cells. The i-th ( 1 \leq i \leq N ) cell he painted is the cell at the a_i-th row and b_i-th column.

Compute the following:

• For each integer j ( 0 \leq j \leq 9 ), how many subrectangles of size 3×3 of the grid contains exactly j black cells, after Snuke painted N cells?

Constraints

• 3 \leq H \leq 10^9
• 3 \leq W \leq 10^9
• 0 \leq N \leq min(10^5,H×W)
• 1 \leq a_i \leq H (1 \leq i \leq N)
• 1 \leq b_i \leq W (1 \leq i \leq N)
• (a_i, b_i) \neq (a_j, b_j) (i \neq j)

Sample Input 1

4 5 8
1 1
1 4
1 5
2 3
3 1
3 2
3 4
4 4

Sample Output 1

0
0
0
2
4
0
0
0
0
0

There are six subrectangles of size 3×3. Two of them contain three black cells each, and the remaining four contain four black cells each.

Sample Input 2

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

Sample Output 2

4
26
22
10
2
0
0
0
0
0

Sample Input 3

1000000000 1000000000 0

Sample Output 3

999999996000000004
0
0
0
0
0
0
0
0
0