Problem Statement

You are given a string S consisting of v and w.

Print the number of "bottoms" in the string S (see the figure at Sample Input/Output).

Constraints

• S is a string consisting of v and w.
• The length of S is between 1 and 100, inclusive.

Sample Input 1

vvwvw

Sample Output 1

7

The image above shows the seven "bottoms" in the string vvwvw.

Sample Input 2

v

Sample Output 2

1

Sample Input 3

wwwvvvvvv

Sample Output 3

12

Problem Statement

The AtCoder railway line has N stations, numbered 1, 2, \ldots, N.

On this line, there are inbound trains that start at station 1 and stop at the stations 2, 3, \ldots, N in order, and outbound trains that start at station N and stop at the stations N - 1, N - 2, \ldots, 1 in order.

Takahashi is about to travel from station X to station Y using only one of the inbound and outbound trains.

Determine whether the train stops at station Z during this travel.

Constraints

• 3 \leq N \leq 100
• 1 \leq X, Y, Z \leq N
• X, Y, and Z are distinct.
• All input values are integers.

Sample Input 1

7 6 1 3

Sample Output 1

Yes

To travel from station 6 to station 1, Takahashi will take an outbound train.

After departing from station 6, the train stops at stations 5, 4, 3, 2, 1 in order, which include station 3, so you should print Yes.

Sample Input 2

10 3 2 9

Sample Output 2

No

Sample Input 3

100 23 67 45

Sample Output 3

Yes

Problem Statement

Bowling pins are numbered 1 through 10. The following figure is a top view of the arrangement of the pins:

Let us call each part between two dotted lines in the figure a column.
For example, Pins 1 and 5 belong to the same column, and so do Pin 3 and 9.

When some of the pins are knocked down, a special situation called split may occur.
A placement of the pins is a split if both of the following conditions are satisfied:

• Pin 1 is knocked down.
• There are two different columns that satisfy both of the following conditions:
  • Each of the columns has one or more standing pins.
  • There exists a column between these columns such that all pins in the column are knocked down.

See also Sample Inputs and Outputs for examples.

Now, you are given a placement of the pins as a string S of length 10. For i = 1, \dots, 10, the i-th character of S is 0 if Pin i is knocked down, and is 1 if it is standing.
Determine if the placement of the pins represented by S is a split.

Constraints

• S is a string of length 10 consisting of 0 and 1.

Sample Input 1

0101110101

Sample Output 1

Yes

In the figure below, the knocked-down pins are painted gray, and the standing pins are painted white:

Between the column containing a standing pin 5 and the column containing a standing pin 6 is a column containing Pins 3 and 9. Since Pins 3 and 9 are both knocked down, the placement is a split.

Sample Input 2

0100101001

Sample Output 2

Yes

Sample Input 3

0000100110

Sample Output 3

No

This placement is not a split.

Sample Input 4

1101110101

Sample Output 4

No

This is not a split because Pin 1 is not knocked down.

Problem Statement

You are given three strings S_1, S_2, S_3 consisting of lowercase English letters, and a string T consisting of 1, 2, 3.

Concatenate the three strings according to the characters in T and print the resulting string. Formally, conform to the following instructions.

• For each integer i such that 1 \leq i \leq |T|, let the string s_i be defined as follows:
  • S_1, if the i-th character of T is 1;
  • S_2, if the i-th character of T is 2;
  • S_3, if the i-th character of T is 3.
• Concatenate the strings s_1, s_2, \dots, s_{|T|} in this order and print the resulting string.

Constraints

• 1 \leq |S_1|, |S_2|, |S_3| \leq 10
• 1 \leq |T| \leq 1000
• S_1, S_2, and S_3 consist of lowercase English letters.
• T consists of 1, 2, and 3.

Sample Input 1

mari
to
zzo
1321

Sample Output 1

marizzotomari

We have s_1 = mari, s_2 = zzo, s_3 = to, s_4 = mari. Concatenate these and print the resulting string: marizzotomari.

Sample Input 2

abra
cad
abra
123

Sample Output 2

abracadabra

Sample Input 3

a
b
c
1

Sample Output 3

a

Problem Statement

You are given length-N integer sequences: A=(A_1,A_2,\ldots,A_N) and B=(B_1,B_2,\ldots,B_N).

You are given Q queries to process in order. The i-th query (1\le i\le Q) is described as follows:

You are given a character c_i and integers X_i,V_i. If c_i= A, change A_{X_i} to V_i; if c_i= B, change B_{X_i} to V_i. Then, output \displaystyle \sum_{k=1}^N \min(A_k,B_k).

Constraints

• 1\le N,Q \le 2 \times 10^5
• 1\le A_i,B_i \le 10^9
• c_i is either A or B.
• 1\le X_i \le N
• 1\le V_i \le 10^9
• All input values are integers.

Sample Input 1

4 3
3 1 4 1
2 7 1 8
A 2 3
B 3 3
A 1 7

Sample Output 1

7
9
9

After the 1st query, A=(3,3,4,1),B=(2,7,1,8). Therefore, output \displaystyle \min(3,2)+\min(3,7) + \min(4 , 1)+\min(1,8) = 7 on the 1st line.

After the 2nd query, A=(3,3,4,1),B=(2,7,3,8). Therefore, output \displaystyle \min(3,2)+\min(3,7) + \min(4 , 3)+\min(1,8) = 9 on the 2nd line.

After the 3rd query, A=(7,3,4,1),B=(2,7,3,8). Therefore, output \displaystyle \min(7,2)+\min(3,7) + \min(4 , 3)+\min(1,8) = 9 on the 3rd line.

Sample Input 2

1 3
1
1000000000
A 1 1
A 1 1
A 1 1

Sample Output 2

1
1
1

Sample Input 3

5 3
100 100 100 100 100
100 100 100 100 100
A 4 21
A 2 99
B 4 57

Sample Output 3

421
420
420