Problem Statement

A mayoral election is being held in AtCoder City. The candidates are Takahashi and Aoki.

There are N valid votes cast for either of the two candidates, and the counting is currently underway. Here, N is an odd number.

The current vote count is T votes for Takahashi and A votes for Aoki.

Determine if the outcome of the election is already decided at this point.

Constraints

• 1 \leq N \leq 99
• N is an odd number.
• 0 \leq T, A \leq N
• T + A \leq N
• All input values are integers.

Sample Input 1

7 4 2

Sample Output 1

Yes

Even if the remaining one vote goes to Aoki, Takahashi will still win. That is, his victory is decided, so print Yes.

Sample Input 2

99 12 48

Sample Output 2

No

Although Aoki currently has more votes, Takahashi would win if he receives the remaining 39 votes. Therefore, print No.

Sample Input 3

1 0 0

Sample Output 3

No

Problem Statement

A string S consisting of lowercase English letters is a good string if and only if it satisfies the following property for all integers i not less than 1:

• There are exactly zero or exactly two different letters that appear exactly i times in S.

Given a string S, determine if it is a good string.

Constraints

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

Sample Input 1

commencement

Sample Output 1

Yes

For the string commencement, the number of different letters that appear exactly i times is as follows:

• i=1: two letters (o and t)
• i=2: two letters (c and n)
• i=3: two letters (e and m)
• i\geq 4: zero letters

Therefore, commencement satisfies the condition of a good string.

Sample Input 2

banana

Sample Output 2

No

For the string banana, there is only one letter that appears exactly one time, which is b, so it does not satisfy the condition of a good string.

Sample Input 3

ab

Sample Output 3

Yes

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

You are given a string S = S_1S_2\ldots S_N of length N consisting of lowercase English letters.

Additionally, you are given Q queries about the string S. For i = 1, 2, \ldots, Q, the i-th query is represented by two integers l_i, r_i and asks the following.

In the substring S_{l_i}S_{l_i+1}\ldots S_{r_i} of S, which ranges from the l_i-th to the r_i-th character, how many places are there where the same lowercase English letter occurs twice in a row? In other words, how many integers p satisfy l_i \leq p \leq r_i-1 and S_p = S_{p+1}?

Print the answer for each of the Q queries.

Constraints

• N and Q are integers.
• 1 \leq N, Q \leq 3 \times 10^5
• S is a string of length N consisting of lowercase English letters.
• l_i and r_i are integers.
• 1 \leq l_i \leq r_i \leq N

Sample Input 1

11 4
mississippi
3 9
4 10
4 6
7 7

Sample Output 1

2
2
0
0

The answers to the four queries are as follows.

• For the first query, S_3S_4\ldots S_9 = ssissip has two places where the same lowercase English letter occurs twice in a row: S_3S_4 = ss and S_6S_7 = ss.
• For the second query, S_4S_5\ldots S_{10} = sissipp has two places where the same lowercase English letter occurs twice in a row: S_6S_7 = ss and S_9S_{10} = pp.
• For the third query, S_4S_5S_6 = sis has zero places where the same lowercase English letter occurs twice in a row.
• For the fourth query, S_7 = s has zero places where the same lowercase English letter occurs twice in a row.

Sample Input 2

5 1
aaaaa
1 5

Sample Output 2

4

S_1S_2\ldots S_5 = aaaaa has four places where the same lowercase English letter occurs twice in a row: S_1S_2 = aa, S_2S_3 = aa, S_3S_4 = aa, and S_4S_5 = aa.