Problem Statement

You are given a string S of length 3.
Print a character that occurs only once in S.
If there is no such character, print -1 instead.

Constraints

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

Sample Input 1

pop

Sample Output 1

o

o occurs only once in pop.

Sample Input 2

abc

Sample Output 2

a

a, b, and c occur once each in abc, so you may print any of them.

Sample Input 3

xxx

Sample Output 3

-1

No character occurs only once in xxx.

Problem Statement

Find a length-N string that satisfies all of the following conditions:

• Each character is - or =.
• It is a palindrome.
• It contains exactly one or exactly two =s. If it contains two =s, they are adjacent.

Such a string is unique.

Constraints

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

Sample Input 1

4

Sample Output 1

-==-

Sample Input 2

7

Sample Output 2

---=---

Problem Statement

AtCoder Kingdom uses a calendar whose year has N months. Month i (1\leq i\leq N) has D _ i days, from day 1 of month i to day D _ i of month i.

How many days in a year of AtCoder have "repdigits" dates?

Here, day j of month i (1\leq i\leq N,1\leq j\leq D _ i) is said to have a repdigit date if and only if all digits in the decimal notations of i and j are the same.

Constraints

• 1\leq N\leq100
• 1\leq D _ i\leq100\ (1\leq i\leq N)
• All input values are integers.

Sample Input 1

12
31 29 31 30 31 30 31 31 30 31 30 31

Sample Output 1

13

In AtCoder Kingdom, the days that have repdigit dates are January 1, January 11, February 2, February 22, March 3, April 4, May 5, June 6, July 7, August 8, September 9, November 1, and November 11, for a total of 13 days.

Sample Input 2

10
10 1 2 3 4 5 6 7 8 100

Sample Output 2

1

In AtCoder Kingdom, only January 1 has a repdigit date.

Sample Input 3

30
73 8 55 26 97 48 37 47 35 55 5 17 62 2 60 23 99 73 34 75 7 46 82 84 29 41 32 31 52 32

Sample Output 3

15

Problem Statement

N horses numbered 1 to N had a race.

All horses started simultaneously, and horse i took T_i seconds from the start to the goal.

Find the numbers of the horses that finished in 1st, 2nd, and 3rd places. It is guaranteed that all T_i are distinct.

Constraints

• 3\leq N \leq 32
• 1\leq T_i \leq 200
• All T_i are distinct.
• All input values are integers.

Sample Input 1

4
100 110 105 95

Sample Output 1

4 1 3

The horses finished in the order 4, 1, 3, 2. Output the numbers for 1st, 2nd, and 3rd places, which are 4, 1, 3, in this order, separated by spaces.

Sample Input 2

8
72 74 69 70 73 75 71 77

Sample Output 2

3 4 7

Problem Statement

There is a queue of snakes. Initially, the queue is empty.

You are given Q queries, which should be processed in the order they are given. There are three types of queries:

• Type 1: Given in the form 1 l. A snake of length l is added to the end of the queue. If the queue was empty before adding, the head position of the newly added snake is 0; otherwise, it is the sum of the head coordinate of the last snake in the queue and the last snake’s length.
• Type 2: Given in the form 2. The snake at the front of the queue leaves the queue. It is guaranteed that the queue is not empty at this time. Let m be the length of the snake that left, then the head coordinate of every snake remaining in the queue decreases by m.
• Type 3: Given in the form 3 k. Output the head coordinate of the snake that is k-th from the front of the queue. It is guaranteed that there are at least k snakes in the queue at this time.

Constraints

• 1 \leq Q \leq 3 \times 10^{5}
• For a query of type 1, 1 \leq l \leq 10^{9}
• For a query of type 2, it is guaranteed that the queue is not empty.
• For a query of type 3, let n be the number of snakes in the queue, then 1 \leq k \leq n.
• All input values are integers.

Sample Input 1

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

Sample Output 1

5
10

• 1st query: A snake of length 5 is added to the queue. Since the queue was empty, the head coordinate of this snake is 0.
• 2nd query: A snake of length 7 is added to the queue. Before adding, the last snake has head coordinate 0 and length 5, so the newly added snake’s head coordinate is 5.
• 3rd query: Output the head coordinate of the snake that is 2nd from the front. Currently, the head coordinates of the snakes in order are 0, 5, so output 5.
• 4th query: A snake of length 3 is added to the queue. Before adding, the last snake has head coordinate 5 and length 7, so the new snake’s head coordinate is 12.
• 5th query: A snake of length 4 is added to the queue. Before adding, the last snake has head coordinate 12 and length 3, so the new snake’s head coordinate is 15.
• 6th query: The snake at the front leaves the queue. The length of the snake that left is 5, so the head coordinate of each remaining snake decreases by 5. The remaining snake’s head coordinate becomes 0, 7, 10.
• 7th query: Output the head coordinate of the snake that is 3rd from the front. Currently, the head coordinates of the snakes in order are 0, 7, 10, so output 10.

Sample Input 2

3
1 1
2
1 3

Sample Output 2

It is possible that there are no queries of type 3.

Sample Input 3

10
1 15
1 10
1 5
2
1 5
1 10
1 15
2
3 4
3 2

Sample Output 3

20
5

Problem Statement

You are given a string S of length N consisting of 0 and 1.
Move the K-th 1-block from the beginning in S to immediately after the (K-1)-th 1-block, and print the resulting string.

It is guaranteed that S contains at least K 1-blocks.

Here is a more precise description.

• Let S_{l\ldots r} denote the substring of S from the l-th character through the r-th character.
• We define a substring S_{l\ldots r} of S to be a 1-block if it satisfies all of the following conditions:
  • S_l = S_{l+1} = \cdots = S_r = 1
  • l = 1 or S_{l-1} = 0
  • r = N or S_{r+1} = 0

• Suppose that all 1-blocks in S are S_{l_1\ldots r_1}, \ldots, S_{l_m\ldots r_m}, where l_1 < l_2 < \cdots < l_m.

  Then, we define the length N string T, obtained by moving the K-th 1-block to immediately after the (K-1)-th 1-block, as follows:

  • T_i = S_i for 1 \leq i \leq r_{K-1}
  • T_i = 1 for r_{K-1} + 1 \leq i \leq r_{K-1} + (r_K - l_K) + 1
  • T_i = 0 for r_{K-1} + (r_K - l_K) + 2 \leq i \leq r_K
  • T_i = S_i for r_K + 1 \leq i \leq N

Constraints

• 1 \leq N \leq 5 \times 10^5
• S is a string of length N consisting of 0 and 1.
• 2 \leq K
• S contains at least K 1-blocks.

Sample Input 1

15 3
010011100011001

Sample Output 1

010011111000001

S has four 1-blocks: from the 2nd to the 2nd character, from the 5th to the 7th character, from the 11th to the 12th character, and from the 15th to the 15th character.

Sample Input 2

10 2
1011111111

Sample Output 2

1111111110

Problem Statement

There is a grid with H rows and W columns. The cell at the i-th row from the top and the j-th column from the left is called cell (i, j).

Every cell is colored white or black. The grid is described by H strings S_1, S_2, \ldots, S_H, each of length W. If the j-th character of S_i is ., cell (i, j) is white; if the j-th character of S_i is #, cell (i, j) is black.

You perform the following operation 10^{100} times.

• Simultaneously apply the following rules to all cells.
  • A cell that is white before the operation becomes black if and only if there exists at least one black cell adjacent to it. Here, cells (x, y) and (x', y') are adjacent if and only if one of them is within the 8-neighborhood of the other, that is, \max(|x-x'|, |y-y'|) = 1.
  • A cell that is black before the operation becomes white.

Find the color of each cell after the operations.

Constraints

• 1 \leq H \times W \leq 10^6
• H and W are positive integers.
• S_i is a string of length W consisting of . and #.

Sample Input 1

3 4
#.#.
.#..
#...

Sample Output 1

#.#.
.#..
#..#

Initially, the grid is as follows.

After one operation, the grid is as follows.

After 10^{100} operations, the grid is as follows.

Sample Input 2

3 3
###
###
###

Sample Output 2

...
...
...

Sample Input 3

5 7
.#.....
.......
..#....
.......
....#..

Sample Output 3

.#.##.#
....#..
#.#.###
#.....#
###.#.#

Problem Statement

You are given a string S of length N consisting of digits from 1 through 9.

For each pair of integers (i,j) \ (1\leq i\leq j\leq N), define f(i, j) as the value obtained by interpreting the substring of S from the i-th through the j-th character as a decimal integer. Find \displaystyle \sum_{i=1}^N \sum_{j=i}^N f(i, j).

Constraints

• 1 \leq N \leq 2 \times 10^5
• N is an integer.
• S is a string of length N consisting of digits from 1 through 9.

Sample Input 1

3
379

Sample Output 1

514

The answer is f(1,1) + f(1,2) + f(1,3) + f(2,2) + f(2,3) + f(3,3) = 3 + 37 + 379 + 7 + 79 + 9 = 514.

Sample Input 2

30
314159265358979323846264338327

Sample Output 2

369673254065355789035427227741

Problem Statement

Tiles are laid out on a coordinate plane. There are two types of tiles: small tiles of size 1\times1 and large tiles of size K\times K, laid out according to the following rules:

• For each pair of integers (i,j), the square \lbrace(x,y)\mid i\leq x\leq i+1\wedge j\leq y\leq j+1\rbrace is contained within either one small tile or one large tile.
  • If \left\lfloor\dfrac iK\right\rfloor+\left\lfloor\dfrac jK\right\rfloor is even, it is contained within a small tile.
  • Otherwise, it is contained within a large tile.

Tiles include their boundaries, and no two different tiles have a positive area of intersection.

For example, when K=3, 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 movement any number of times:

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

Each time he crosses from one tile to another, he must pay a toll of 1.

Determine the minimum toll Takahashi must pay to reach the point (T_x+0.5,T_y+0.5).

Constraints

• 1\leq K\leq10^{16}
• 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

3
7 2
1 6

Sample Output 1

5

For example, he can move as follows, paying a toll of 5.

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

The toll paid cannot be 4 or less, so print 5.

Sample Input 2

1
41 42
13 56

Sample Output 2

42

When he moves the shortest distance, he will always pay a toll of 42.

The toll paid cannot be 41 or less, so print 42.

Sample Input 3

100
100 99
199 1

Sample Output 3

0

There are cases where no toll needs to be paid.

Sample Input 4

96929423
5105216413055191 10822465733465225
1543712011036057 14412421458305526

Sample Output 4

79154049