Problem Statement

You are given a string S of length 3 consisting of uppercase English letters.

Determine whether it is possible to rearrange the characters in S to make it match the string ABC.

Constraints

• S is a string of length 3 consisting of uppercase English letters.

Sample Input 1

BAC

Sample Output 1

Yes

You can make S match ABC by swapping the first and second characters of S.

Sample Input 2

AAC

Sample Output 2

No

You cannot make S match ABC no matter how you rearrange the characters.

Sample Input 3

ABC

Sample Output 3

Yes

Sample Input 4

ARC

Sample Output 4

No

Problem Statement

You are given a string S of length N.
Output the string obtained by removing all leading consecutive os from S.
If all characters in S are o, output an empty string.

Constraints

• N is an integer satisfying 1 \le N \le 50.
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

7
ooparts

Sample Output 1

parts

Removing all leading consecutive os from ooparts gives parts.

Sample Input 2

6
abcooo

Sample Output 2

abcooo

The first character may not be o.

Sample Input 3

5
ooooo

Sample Output 3

All characters may be o.

Problem Statement

Given a non-negative integer X, perform the following operation for i=1,2,\dots,K in this order and find the resulting X.

• Round X off to the nearest 10^i.
  • Formally, replace X with Y that is "the largest multiple of 10^i that minimizes |Y-X|."
  • Here are some examples:
    • Rounding 273 off to the nearest 10^2 yields 300.
    • Rounding 999 off to the nearest 10^3 yields 1000.
    • Rounding 100 off to the nearest 10^{10} yields 0.
    • Rounding 1015 off to the nearest 10^1 yields 1020.

Constraints

• X and K are integers.
• 0 \le X < 10^{15}
• 1 \le K \le 15

Sample Input 1

2048 2

Sample Output 1

2100

X changes as 2048 \rightarrow 2050 \rightarrow 2100 by the operations.

Sample Input 2

1 15

Sample Output 2

0

Sample Input 3

999 3

Sample Output 3

1000

Sample Input 4

314159265358979 12

Sample Output 4

314000000000000

X may not fit into a 32-bit integer type.

Problem Statement

You are given N strings S_1, S_2, \ldots, S_N consisting of lowercase English letters.

Define N digits C_1, C_2, \ldots, C_N as follows:

• If the first character of S_i is one of a, b, c, then C_i= 2
• If the first character of S_i is one of d, e, f, then C_i= 3
• If the first character of S_i is one of g, h, i, then C_i= 4
• If the first character of S_i is one of j, k, l, then C_i= 5
• If the first character of S_i is one of m, n, o, then C_i= 6
• If the first character of S_i is one of p, q, r, s, then C_i= 7
• If the first character of S_i is one of t, u, v, then C_i= 8
• If the first character of S_i is one of w, x, y, z, then C_i= 9

Output the string obtained by concatenating C_1, C_2, \ldots, C_N in this order.

Constraints

• 1 \leq N \leq 10
• N is an integer.
• S_i is a string of length between 1 and 10, inclusive, consisting of lowercase English letters.

Sample Input 1

2
algorithm heuristic

Sample Output 1

24

• The first character of S_1= algorithm is a, so C_1= 2.
• The first character of S_2= heuristic is h, so C_2= 4.

Thus, output 24, which is their concatenation.

Sample Input 2

3
i love you

Sample Output 2

459

Problem Statement

Given is a string S consisting of lowercase English letters. Determine whether adding some number of a's (possibly zero) at the beginning of S can make it a palindrome.

Here, a string of length N, A=A_1A_2\ldots A_N, is said to be a palindrome when A_i=A_{N+1-i} for every 1\leq i\leq N.

Constraints

• 1 \leq \lvert S \rvert \leq 10^6
• S consists of lowercase English letters.

Sample Input 1

kasaka

Sample Output 1

Yes

By adding one a at the beginning of kasaka, we have akasaka, which is a palindrome, so Yes should be printed.

Sample Input 2

atcoder

Sample Output 2

No

Adding any number of a's at the beginning of atcoder does not make it a palindrome.

Sample Input 3

php

Sample Output 3

Yes

php itself is a palindrome. Adding zero a's at the beginning of S is allowed, so Yes should be printed.

Problem Statement

There is a grid with H rows and W columns. Let (i, j) denote the square at the i-th row from the top and the j-th column from the left.
Initially, there was one cookie on each square inside a rectangle whose height and width were at least 2 squares long, and no cookie on the other squares.
Formally, there was exactly one quadruple of integers (a,b,c,d) that satisfied all of the following conditions.

• 1 \leq a \lt b \leq H
• 1 \leq c \lt d \leq W
• There was one cookie on each square (i, j) such that a \leq i \leq b, c \leq j \leq d, and no cookie on the other squares.

However, Snuke took and ate one of the cookies on the grid.
The square that contained that cookie is now empty.

As the input, you are given the state of the grid after Snuke ate the cookie.
The state of the square (i, j) is given as the character S_{i,j}, where # means a square with a cookie, and . means a square without one.
Find the square that contained the cookie eaten by Snuke. (The answer is uniquely determined.)

Constraints

• 2 \leq H, W \leq 500
• S_{i,j} is # or ..

Sample Input 1

5 6
......
..#.#.
..###.
..###.
......

Sample Output 1

2 4

Initially, cookies were on the squares inside the rectangle with (2, 3) as the top-left corner and (4, 5) as the bottom-right corner, and Snuke ate the cookie on (2, 4). Thus, you should print (2, 4).

Sample Input 2

3 2
#.
##
##

Sample Output 2

1 2

Initially, cookies were placed on the squares inside the rectangle with (1, 1) as the top-left corner and (3, 2) as the bottom-right corner, and Snuke ate the cookie at (1, 2).

Sample Input 3

6 6
..####
..##.#
..####
..####
..####
......

Sample Output 3

2 5

Problem Statement

The pattern of AtCoder's wallpaper can be represented on the xy-plane as follows:

• The plane is divided by the following three types of lines:
  • x = n (where n is an integer)
  • y = n (where n is an even number)
  • x + y = n (where n is an even number)
• Each region is painted black or white. Any two regions adjacent along one of these lines are painted in different colors.
• The region containing (0.5, 0.5) is painted black.

The following figure shows a part of the pattern.

You are given integers A, B, C, D. Consider a rectangle whose sides are parallel to the x- and y-axes, with its bottom-left vertex at (A, B) and its top-right vertex at (C, D). Calculate the area of the regions painted black inside this rectangle, and print twice that area.

It can be proved that the output value will be an integer.

Constraints

• -10^9 \leq A, B, C, D \leq 10^9
• A < C and B < D.
• All input values are integers.

Sample Input 1

0 0 3 3

Sample Output 1

10

We are to find the area of the black-painted region inside the following square:

The area is 5, so print twice that value: 10.

Sample Input 2

-1 -2 1 3

Sample Output 2

11

The area is 5.5, which is not an integer, but the output value is an integer.

Sample Input 3

-1000000000 -1000000000 1000000000 1000000000

Sample Output 3

4000000000000000000

This is the case with the largest rectangle, where the output still fits into a 64-bit signed integer.

Problem Statement

We have a grid with 2 rows and L columns. Let (i,j) denote the square at the i-th row from the top (i\in\lbrace1,2\rbrace) and j-th column from the left (1\leq j\leq L). (i,j) has an integer x _ {i,j} written on it.

Find the number of integers j such that x _ {1,j}=x _ {2,j}.

Here, the description of x _ {i,j} is given to you as the run-length compressions of (x _ {1,1},x _ {1,2},\ldots,x _ {1,L}) and (x _ {2,1},x _ {2,2},\ldots,x _ {2,L}) into sequences of lengths N _ 1 and N _ 2, respectively: ((v _ {1,1},l _ {1,1}),\ldots,(v _ {1,N _ 1},l _ {1,N _ 1})) and ((v _ {2,1},l _ {2,1}),\ldots,(v _ {2,N _ 2},l _ {2,N _ 2})).

Here, the run-length compression of a sequence A is a sequence of pairs (v _ i,l _ i) of an element v _ i of A and a positive integer l _ i obtained as follows.

1. Split A between each pair of different adjacent elements.
2. For each sequence B _ 1,B _ 2,\ldots,B _ k after the split, let v _ i be the element of B _ i and l _ i be the length of B _ i.

Constraints

• 1\leq L\leq 10 ^ {12}
• 1\leq N _ 1,N _ 2\leq 10 ^ 5
• 1\leq v _ {i,j}\leq 10 ^ 9\ (i\in\lbrace1,2\rbrace,1\leq j\leq N _ i)
• 1\leq l _ {i,j}\leq L\ (i\in\lbrace1,2\rbrace,1\leq j\leq N _ i)
• v _ {i,j}\neq v _ {i,j+1}\ (i\in\lbrace1,2\rbrace,1\leq j\lt N _ i)
• l _ {i,1}+l _ {i,2}+\cdots+l _ {i,N _ i}=L\ (i\in\lbrace1,2\rbrace)
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

4

The grid is shown below.

We have four integers j such that x _ {1,j}=x _ {2,j}: j=1,2,5,8. Thus, you should print 4.

Sample Input 2

10000000000 1 1
1 10000000000
1 10000000000

Sample Output 2

10000000000

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

Sample Input 3

1000 4 7
19 79
33 463
19 178
33 280
19 255
33 92
34 25
19 96
12 11
19 490
33 31

Sample Output 3

380

Problem Statement

You are given an undirected tree T with N vertices, numbered 1, 2, \ldots, N. The i-th edge is an undirected edge connecting vertices A_i and B_i.

A graph is defined to be an alkane if and only if it satisfies the following conditions:

• The graph is an undirected tree.
• Every vertex has degree 1 or 4, and there is at least one vertex of degree 4.

Determine whether there exists a subgraph of T that is an alkane, and if so, find the maximum number of vertices in such a subgraph.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq N
• The given graph is an undirected tree.
• All input values are integers.

Sample Input 1

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

Sample Output 1

8

Let (u, v) denote an undirected edge between vertices u and v.

A subgraph consisting of vertices 1,2,3,4,6,7,8,9 and edges (1,2),(2,3),(3,4),(2,6),(2,7),(3,8),(3,9) is an alkane.

Sample Input 2

7
1 2
1 3
2 4
2 5
3 6
3 7

Sample Output 2

-1

Sample Input 3

15
8 5
2 9
1 12
6 11
9 3
15 1
7 12
7 13
10 5
6 9
5 1
1 9
4 5
6 14

Sample Output 3

11