Problem Statement

The frequency of a sound doubles for every increase of 1 octave in pitch.

If the pitch of a sound with frequency X hertz is raised by Y octaves, what will its frequency be in hertz?

Constraints

• 1 \leq X \leq 444
• 1 \leq Y \leq 3
• All input values are integers.

Sample Input 1

110 2

Sample Output 1

440

For a sound 2 octaves above a sound with frequency 110 hertz, its frequency is 110 \times 2 \times 2 = 440 hertz.

Sample Input 2

233 3

Sample Output 2

1864

For a sound 3 octaves above a sound with frequency 233 hertz, its frequency is 233 \times 2 \times 2 \times 2 = 1864 hertz.

Sample Input 3

432 1

Sample Output 3

864

For a sound 1 octave above a sound with frequency 432 hertz, its frequency is 432 \times 2 = 864 hertz.

Problem Statement

The versions of a certain OS in chronological order are "Ocelot", "Serval", "Lynx".
Determine whether version X is the same as or newer than version Y.

Constraints

• Each of X and Y is one of "Ocelot", "Serval", "Lynx" (without quotation marks).

Sample Input 1

Serval Ocelot

Sample Output 1

Yes

Version Serval is the same as or newer than version Ocelot. Therefore, print Yes.

Sample Input 2

Serval Lynx

Sample Output 2

No

Version Serval is not the same as nor newer than version Lynx. Therefore, print No.

Sample Input 3

Ocelot Ocelot

Sample Output 3

Yes

Version Ocelot itself is the same as or newer than version Ocelot. Therefore, print Yes.

Problem Statement

In the Kingdom of AtCoder, the eldest son is always given the name Taro. No one else is given the name Taro. The eldest son is the earliest born male child in each family.

There are N families in the Kingdom, and M babies were born. Before the M babies were born, none of the N families had had any babies.

Information about the babies is given in chronological order of their birth.

The i-th baby born was born in family A_i, and the baby is male if B_i is M, and female if it is F.

Determine for each of the M babies whether the name given is Taro.

Constraints

• 1\leq N,M\leq 100
• 1\leq A_i\leq N
• B_i is M or F.
• All numbers in the input are integers.

Sample Input 1

2 4
1 M
1 M
2 F
2 M

Sample Output 1

Yes
No
No
Yes

The first baby is the earliest born boy in family 1, so he is named Taro.

The second baby is not the earliest born boy in family 1, so he is not named Taro.

The third baby is a girl, so she is not named Taro.

The fourth baby is the earliest born boy in family 2, so he is named Taro. Note that the third baby is also born in family 2, but it is the earliest born boy who is named Taro.

Sample Input 2

4 7
2 M
3 M
1 F
4 F
4 F
1 F
2 M

Sample Output 2

Yes
Yes
No
No
No
No
No

Problem Statement

One day, Takahashi performed N operations on a certain web site.

The i‑th operation (1 \le i \le N) is represented by a string S_i, which is one of the following:

• S _ i= login: He performs a login operation and becomes logged in to the site.
• S _ i= logout: He performs a logout operation and becomes not logged in to the site.
• S _ i= public: He accesses a public page of the site.
• S _ i= private: He accesses a private page of the site.

The site returns an authentication error if and only if he accesses a private page while he is not logged in.

Logging in again while already logged in, or logging out again while already logged out, does not cause an error. Even after an authentication error is returned, he continues performing the remaining operations.

Initially, he is not logged in.

Print the number of operations among the N operations at which he receives an authentication error.

Constraints

• 1 \le N \le 100
• N is an integer.
• Each S_i is one of login, logout, public, private. (1 \le i \le N)

Sample Input 1

6
login
private
public
logout
private
public

Sample Output 1

1

The result of each operation is as follows:

• Takahashi becomes logged in.
• He accesses a private page. He is logged in, so no error is returned.
• He accesses a public page.
• He becomes logged out.
• He accesses a private page. He is not logged in, so an authentication error is returned.
• He accesses a public page.

An authentication error occurs only at the 5th operation, so print 1.

Sample Input 2

4
private
private
private
logout

Sample Output 2

3

If he tries to access private pages consecutively while not logged in, he receives an authentication error for each such operation.

Note that logging out again while already logged out does not cause an authentication error.

Sample Input 3

20
private
login
private
logout
public
logout
logout
logout
logout
private
login
login
private
login
private
login
public
private
logout
private

Sample Output 3

3

Problem Statement

This problem is a sub-problem of Problem F (Operate K), with K=1.
You can solve this problem by submitting a correct solution for Problem F to this problem.

Determine whether it is possible to perform the following operation on string S between 0 and K times, inclusive, to make it identical to string T.

• Choose one of the following three operations and execute it.
  • Insert any one character at any position in S (possibly the beginning or end).
  • Delete one character from S.
  • Choose one character in S and replace it with another character.

Constraints

• Each of S and T is a string of length between 1 and 500000, inclusive, consisting of lowercase English letters.
• \color{red}{K=1}

Sample Input 1

1
abc
agc

Sample Output 1

Yes

Replacing the second character b of abc with g converts abc to agc in one operation.

Sample Input 2

1
abc
awtf

Sample Output 2

No

abc cannot be converted to awtf in one operation.

Sample Input 3

1
abc
ac

Sample Output 3

Yes

Deleting the second character b of abc converts abc to ac in one operation.

Sample Input 4

1
back
black

Sample Output 4

Yes

Inserting l between the first and second characters of back converts back to black in one operation.

Sample Input 5

1
same
same

Sample Output 5

Yes

It is also possible that S = T from the beginning.

Sample Input 6

1
leap
read

Sample Output 6

No

Problem Statement

You are given a length-N integer sequence A = (A_1, A_2, \dots, A_N).

Compute the value of \displaystyle \sum_{1\leq i< j\leq N} A_iA_j.

Constraints

• 2 \le N \le 3 \times 10^5
• 1 \le A_i \le 10^4
• All input values are integers.

Sample Input 1

3
4 2 3

Sample Output 1

26

We have \displaystyle \sum_{1\leq i< j\leq N} A_iA_j=A_1A_2+A_1A_3+A_2A_3=4\cdot 2+4\cdot 3+2\cdot 3=26.

Sample Input 2

2
9 45

Sample Output 2

405

Sample Input 3

10
7781 8803 8630 9065 8831 9182 8593 7660 7548 8617

Sample Output 3

3227530139

Problem Statement

There is a number line, and initially person 0 is standing alone at coordinate 0.

From now on, persons 1,2,\dots,N will arrive in this order and stand on the number line.
Person i stands at coordinate X_i. Here, X_i \ge 1, and X_i is distinct for all persons.

Each time a person arrives, answer the following question.

• Suppose that currently r+1 persons 0,1,\dots,r are standing on the number line.
• Here, define d_i as the distance to the nearest other person from person i.
  • More formally, \displaystyle d_i = \min_{0 \le j \le r, j \neq i} \vert X_i - X_j \vert.
• Find the sum of this d, that is, \displaystyle \sum_{i=0}^r d_i.

Constraints

• All input values are integers.
• 1 \le N \le 5 \times 10^5
• 1 \le X_i \le 10^9
• X_i \neq X_j if i \neq j.

Sample Input 1

10
5 2 7 4 108728325 390529120 597713292 322456626 845148281 812604915

Sample Output 1

10
7
8
8
108728326
390529121
523096670
452057486
699492475
517144218

In this input, 10 persons arrive.
The first four persons are explained below.

• When person 1 arrives, there are persons at coordinates 0,5.
  • The required value is 5+5=10.
• When person 2 arrives, there are persons at coordinates 0,2,5.
  • The required value is 2+2+3=7.
• When person 3 arrives, there are persons at coordinates 0,2,5,7.
  • The required value is 2+2+2+2=8.
• When person 4 arrives, there are persons at coordinates 0,2,4,5,7.
  • The required value is 2+2+1+1+2=8.

Problem Statement

You are given a sequence A=(A_0,A_1,\ldots,A_{N-1}) of length N.
There is an initially empty dish. Takahashi is going to repeat the following operation K times.

• Let X be the number of candies on the dish. He puts A_{(X\bmod N)} more candies on the dish. Here, X\bmod N denotes the remainder when X is divided by N.

Find how many candies are on the dish after the K operations.

Constraints

• 2 \leq N \leq 2\times 10^5
• 1 \leq K \leq 10^{12}
• 1 \leq A_i\leq 10^6
• All values in input are integers.

Sample Input 1

5 3
2 1 6 3 1

Sample Output 1

11

The number of candies on the dish transitions as follows.

• In the 1-st operation, we have X=0, so A_{(0\mod 5)}=A_0=2 more candies will be put on the dish.
• In the 2-nd operation, we have X=2, so A_{(2\mod 5)}=A_2=6 more candies will be put on the dish.
• In the 3-rd operation, we have X=8, so A_{(8\mod 5)}=A_3=3 more candies will be put on the dish.

Thus, after the 3 operations, there will be 11 candies on the dish. Note that you must not print the remainder divided by N.

Sample Input 2

10 1000000000000
260522 914575 436426 979445 648772 690081 933447 190629 703497 47202

Sample Output 2

826617499998784056

The answer may not fit into a 32-bit integer type.

Problem Statement

We have a typewriter with N rows. The keys in the i-th row from the top can type the characters in a string S_i.

Let us use this keyboard to enter a string, as follows.

• First, choose an integer 1 \le k \le N.
• Then, start with an empty string and only use the keys in the k-th row from the top to enter a string of length exactly L.

How many strings of length L can be entered in this way? Since the answer can be enormous, print it modulo 998244353.

Constraints

• N and L are integers.
• 1 \le N \le 18
• 1 \le L \le 10^9
• S_i is a (not necessarily contiguous) non-empty subsequence of abcdefghijklmnopqrstuvwxyz.

Sample Input 1

2 2
ab
ac

Sample Output 1

7

We can enter seven strings: aa, ab, ac, ba, bb, ca, cc.

Sample Input 2

4 3
abcdefg
hijklmnop
qrstuv
wxyz

Sample Output 2

1352

Sample Input 3

5 1000000000
abc
acde
cefg
abcfh
dghi

Sample Output 3

346462871

Be sure to print the answer modulo 998244353.