Problem Statement

You are given a string S consisting of lowercase English letters.

Uppercase each character of S and print the resulting string T.

Constraints

• S is a string consisting of lowercase English letters whose length is between 1 and 100, inclusive.

Sample Input 1

abc

Sample Output 1

ABC

Uppercase each character of abc, and you have ABC.

Sample Input 2

a

Sample Output 2

A

Sample Input 3

abcdefghjiklnmoqprstvuwxyz

Sample Output 3

ABCDEFGHJIKLNMOQPRSTVUWXYZ

Problem Statement

You are given a string S consisting of lowercase English letters and the character ..
Print the last substring when S is split by .s.
In other words, print the longest suffix of S that does not contain ..

Constraints

• S is a string of length between 2 and 100, inclusive, consisting of lowercase English letters and ..
• S contains at least one ..
• S does not end with ..

Sample Input 1

atcoder.jp

Sample Output 1

jp

The longest suffix of atcoder.jp that does not contain . is jp.

Sample Input 2

translate.google.com

Sample Output 2

com

S may contain multiple .s.

Sample Input 3

.z

Sample Output 3

z

S may start with ..

Sample Input 4

..........txt

Sample Output 4

txt

S may contain consecutive .s.

Problem Statement

There are N boxes numbered 1,2,\dots,N. Initially, all boxes are empty.

Q balls will come in order.
Takahashi will put the balls into the boxes according to the sequence X=(X_1,X_2,\dots,X_Q).
Specifically, he performs the following process for the i-th ball:

• If X_i \ge 1: Put this ball into box X_i.
• If X_i = 0: Put this ball into the box with the smallest number among those containing the fewest balls.

Find which box each ball was put into.

Constraints

• All input values are integers.
• 1 \le N \le 100
• 1 \le Q \le 100
• 0 \le X_i \le N

Sample Input 1

4 5
2 0 3 0 0

Sample Output 1

2 1 3 4 1

There are 4 boxes, and 5 balls come.

• Initially, all boxes are empty.
  • The numbers of balls in box 1,2,3,4 are 0,0,0,0, respectively.
• Since X_1=2, put the 1st ball into box 2.
  • The numbers of balls in box 1,2,3,4 are 0,1,0,0, respectively.
• Since X_2=0, put the 2nd ball into box 1, which has the smallest number among those containing the fewest balls.
  • The numbers of balls in box 1,2,3,4 are 1,1,0,0, respectively.
• Since X_3=3, put the 3rd ball into box 3.
  • The numbers of balls in box 1,2,3,4 are 1,1,1,0, respectively.
• Since X_4=0, put the 4th ball into box 4, which has the smallest number among those containing the fewest balls.
  • The numbers of balls in box 1,2,3,4 are 1,1,1,1, respectively.
• Since X_5=0, put the 5th ball into box 1, which has the smallest number among those containing the fewest balls.
  • The numbers of balls in box 1,2,3,4 are 2,1,1,1, respectively.

The balls were put into boxes 2,1,3,4,1 in order. Thus, output 2 1 3 4 1.

Sample Input 2

3 7
1 1 0 0 0 0 0

Sample Output 2

1 1 2 3 2 3 1

Sample Input 3

6 20
4 6 0 3 4 2 6 5 2 3 0 3 2 5 0 3 5 0 2 0

Sample Output 3

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

Problem Statement

Takahashi is trying to create a game inspired by baseball, but he is having difficulty writing the code.
Write a program for Takahashi that solves the following problem.

There are 4 squares called Square 0, Square 1, Square 2, and Square 3. Initially, all squares are empty.
There is also an integer P; initially, P = 0.
Given a sequence of positive integers A = (A_1, A_2, \dots, A_N), perform the following operations for i = 1, 2, \dots, N in this order:

1. Put a piece on Square 0.
2. Advance every piece on the squares A_i squares ahead. In other words, if Square x has a piece, move the piece to Square (x + A_i).
   If, however, the destination square does not exist (i.e. x + A_i is greater than or equal to 4) for a piece, remove it. Add to P the number of pieces that have been removed.

Print the value of P after all the operations have been performed.

Constraints

• 1 \leq N \leq 100
• 1 \leq A_i \leq 4
• All values in input are integers.

Sample Input 1

4
1 1 3 2

Sample Output 1

3

The operations are described below. After all the operations have been performed, P equals 3.

• The operations for i=1:
  1. Put a piece on Square 0. Now, Square 0 has a piece.
  2. Advance every piece on the squares 1 square ahead. After these moves, Square 1 has a piece.
• The operations for i=2:
  1. Put a piece on Square 0. Now, Squares 0 and 1 have a piece.
  2. Advance every piece on the squares 1 square ahead. After these moves, Squares 1 and 2 have a piece.
• The operations for i=3:
  1. Put a piece on Square 0. Now, Squares 0, 1, and 2 have a piece.
  2. Advance every piece on the squares 3 squares ahead.
     Here, for the pieces on Squares 1 and 2, the destination squares do not exist (since 1+3=4 and 2+3=5), so remove these pieces and add 2 to P. P now equals 2. After these moves, Square 3 has a piece.
• The operations for i=4:
  1. Put a piece on Square 0. Now, Squares 0 and 3 have a piece.
  2. Advance every piece on the squares 2 squares ahead.
     Here, for the piece on Square 3, the destination square does not exist (since 3+2=5), so remove this piece and add 1 to P. P now equals 3.
     After these moves, Square 2 has a piece.

Sample Input 2

3
1 1 1

Sample Output 2

0

The value of P may not be updated by the operations.

Sample Input 3

10
2 2 4 1 1 1 4 2 2 1

Sample Output 3

8

Problem Statement

There are N squares arranged in a row from left to right. Initially, all squares are painted white.

Process Q queries in order. The i-th query gives an integer A_i between 1 and N, inclusive, and performs the following operation:

Flip the color of the A_i-th square from the left. Specifically, if the A_i-th square from the left is painted white, paint it black; if it is painted black, paint it white.
Then, find the number of intervals of consecutively painted black squares.

Here, an interval of consecutively painted black squares is a pair of integers (l,r) (1\leq l\leq r\leq N) that satisfy all of the following:

• The l-th, (l+1)-th, \ldots, r-th squares from the left are all painted black.
• Either l=1, or the (l-1)-th square from the left is painted white.
• Either r=N, or the (r+1)-th square from the left is painted white.

Constraints

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

Sample Input 1

5 7
2 3 3 5 1 5 2

Sample Output 1

1
1
1
2
2
1
1

Below, the i-th square from the left is referred to as square i.
After each query, the state is as follows:

• After the 1st query, only square 2 is painted black. There is 1 interval of consecutively painted black squares: (l,r)=(2,2).
• After the 2nd query, squares 2,3 are painted black. There is 1 interval of consecutively painted black squares: (l,r)=(2,3).
• After the 3rd query, only square 2 is painted black. There is 1 interval of consecutively painted black squares: (l,r)=(2,2).
• After the 4th query, squares 2,5 are painted black. There are 2 intervals of consecutively painted black squares: (l,r)=(2,2), (5,5).
• After the 5th query, squares 1,2,5 are painted black. There are 2 intervals of consecutively painted black squares: (l,r)=(1,2), (5,5).
• After the 6th query, only squares 1,2 are painted black. There is 1 interval of consecutively painted black squares: (l,r)=(1,2).
• After the 7th query, only square 1 is painted black. There is 1 interval of consecutively painted black squares: (l,r)=(1,1).

Thus, output 1,1,1,2,2,1,1 separated by newlines.

Sample Input 2

1 2
1 1

Sample Output 2

1
0

After the 2nd query, all squares are painted white, so output 0 on the 2nd line.

Sample Input 3

3 3
1 3 2

Sample Output 3

1
2
1