Problem Statement

There was a contest with N problems. The i-th (1\leq i\leq N) problem was worth A_i points.

Snuke took part in this contest and solved M problems: the B_1-th, B_2-th, \ldots, and B_M-th ones. Find his total score.

Here, the total score is defined as the sum of the points for the problems he solved.

Constraints

• 1\leq M \leq N \leq 100
• 1\leq A_i \leq 100
• 1\leq B_1 < B_2 < \ldots < B_M \leq N
• All values in the input are integers.

Sample Input 1

3 2
10 20 30
1 3

Sample Output 1

40

Snuke solved the 1-st and 3-rd problems, which are worth 10 and 30 points, respectively. Thus, the total score is 10+30=40 points.

Sample Input 2

4 1
1 1 1 100
4

Sample Output 2

100

Sample Input 3

8 4
22 75 26 45 72 81 47 29
4 6 7 8

Sample Output 3

202

Problem Statement

In the figure shown in the image below, are the points numbered a and b directly connected by a line segment?

Constraints

• 1 \leq a \lt b \leq 10
• a and b are integers.

Sample Input 1

4 5

Sample Output 1

Yes

In the figure shown in the Problem Statement, the points numbered 4 and 5 are directly connected by a line segment.
Thus, Yes should be printed.

Sample Input 2

3 5

Sample Output 2

No

In the figure shown in the Problem Statement, the points numbered 3 and 5 are not directly connected by a line segment.
Thus, No should be printed.

Sample Input 3

1 10

Sample Output 3

Yes

Problem Statement

There are 7 points A, B, C, D, E, F, and G on a straight line, in this order. (See also the figure below.)
The distances between adjacent points are as follows.

• Between A and B: 3
• Between B and C: 1
• Between C and D: 4
• Between D and E: 1
• Between E and F: 5
• Between F and G: 9

You are given two uppercase English letters p and q. Each of p and q is A, B, C, D, E, F, or G, and it holds that p \neq q.
Find the distance between the points p and q.

Constraints

• Each of p and q is A,B,C,D,E,F, or G.
• p \neq q

Sample Input 1

A C

Sample Output 1

4

The distance between the points A and C is 3 + 1 = 4.

Sample Input 2

G B

Sample Output 2

20

The distance between the points G and B is 9 + 5 + 1 + 4 + 1 = 20.

Sample Input 3

C F

Sample Output 3

10

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

Among the positive integers that consist of 0's and 2's when written in base 10, find the K-th smallest integer.

Constraints

• K is an integer between 1 and 10^{18} (inclusive).

Sample Input 1

3

Sample Output 1

22

The positive integers that consist of 0's and 2's when written in base 10 are 2,20,22,\dots in ascending order.
The (K=) 3-rd of them, which is 22, should be printed.

Sample Input 2

11

Sample Output 2

2022

Sample Input 3

923423423420220108

Sample Output 3

220022020000202020002022022000002020002222002200002022002200

Note that the exact value of the answer must be printed as an integer, even if it is big.

Problem Statement

You are given a string S consisting of a, b, c.

Find the number of non-empty substrings of S in which no two adjacent characters are the same, modulo 998244353.

Two substrings are considered distinct if they are taken from different positions, even if they are identical as strings.

Constraints

• S is a string of length between 1 and 3 \times 10^5, inclusive, consisting of a, b, c.

Sample Input 1

abbc

Sample Output 1

6

The substrings in which no two adjacent characters are the same are the following six:

• a (from the 1st to the 1st character of S)
• b (from the 2nd to the 2nd character of S)
• b (from the 3rd to the 3rd character of S)
• c (from the 4th to the 4th character of S)
• ab (from the 1st to the 2nd character of S)
• bc (from the 3rd to the 4th character of S)

Note that, as with the 2nd and 3rd entries, two substrings are considered distinct if they are taken from different positions, even if they are identical as strings.

Sample Input 2

cabcabcbcaccacbcbcaabacbacaabccacbccbcacbacbacabcacabcaccaaaaabababcbabacaccabbcacbcbcbcababcbcbabca

Sample Output 2

760

Problem Statement

There is a grid with H rows and W columns. Let (i,j) denote the cell at the i-th row from the top and j-th column from the left. The state of each cell is represented by a character A_{i,j}, with the following meanings:

• . : Empty cell.
• # : Obstacle cell.
• S : Start cell.
• G : Goal cell.
• o : Open door cell.
• x : Closed door cell.
• ? : Switch cell.

Takahashi can move from his current cell to an adjacent cell (up, down, left, right) that is neither an obstacle cell nor a closed door cell in one operation.

Also, every time he moves to a switch cell, all open door cells become closed door cells, and all closed door cells become open door cells.

Determine whether he can move from the initial state of being at the start cell to being at the goal cell, and if possible, find the minimum number of operations required.

Constraints

• 1\le H,W \le 500
• H and W are integers.
• Each A_{i,j} is one of ., #, S, G, o, x, ?.
• S and G each appear exactly once in A_{i,j}.

Sample Input 1

2 4
S.xG
#?o.

Sample Output 1

5

By moving from (1,1) to (1,2),(2,2),(1,2),(1,3),(1,4) in that order, he can reach the goal cell in five operations.

Sample Input 2

1 5
So?oG

Sample Output 2

-1

No matter how he operates, he cannot reach the goal cell. Therefore, output -1.

Sample Input 3

5 5
Sx?x?
o#o#x
?o?o?
x#x#o
?x?oG

Sample Output 3

10

Problem Statement

You are given an integer sequence P=(P _ 1,P _ 2,\ldots,P _ N) that is a permutation of (1,2,\ldots,N). Here, it is guaranteed that P is not equal to (1,2,\ldots,N).

You want to perform the following operation zero or more times to make P match the sequence (1,2,\ldots,N):

• Choose a pair of integers (i,j) satisfying 1\le i\lt j\le N. Swap the values of P _ i and P _ j.

Let K be the minimum number of operations required to make P match the sequence (1,2,\ldots,N).

Find the number of operations that can be the first operation in a sequence of operations that makes P match the sequence (1,2,\ldots,N) in K operations. Two operations are distinguished if and only if the chosen pairs of integers (i,j) are different.

Constraints

• 2\le N\le3\times10 ^ 5
• 1\le P _ i\le N\ (1\le i\le N)
• P _ i\ne P _ j\ (1\le i\lt j\le N)
• There exists 1\le i\le N such that i\ne P _ i.
• All input values are integers.

Sample Input 1

5
3 1 4 2 5

Sample Output 1

6

For example, the goal can be achieved in three operations as follows:

• Choose (i,j)=(1,2). P becomes (1,3,4,2,5).
• Choose (i,j)=(2,4). P becomes (1,2,4,3,5).
• Choose (i,j)=(3,4). P becomes (1,2,3,4,5).

The goal cannot be achieved in two or fewer operations, so K=3.

As explained above, choosing (1,2) for the first operation allows the goal to be achieved in three operations. Additionally, if one of (1,3),(1,4),(2,3),(2,4),(3,4) is chosen for the first operation, then by performing the next two operations appropriately, P can be made equal to (1,2,3,4,5).

Therefore, print 6.

Sample Input 2

2
2 1

Sample Output 2

1

Sample Input 3

20
15 5 13 17 9 11 20 4 14 16 6 3 8 19 12 7 10 18 2 1

Sample Output 3

77

Problem Statement

There is a sequence A. Initially, A=(0). (That is, A is a sequence of length 1 containing 0 as its only element).

You are given Q queries to process in order. The i-th query (1\leq i\leq Q) has one of the following forms:

• 1 x: Insert i immediately after the location where x appears in A. Specifically, let A_j be the j-th element of the current A and n be the length of A. For p such that A_p=x, update A to (A_1,\dots,A_p,i,A_{p+1},\dots,A_n). It is guaranteed that A contains x immediately before processing this query.
• 2 x y: Remove all elements between x and y in A, and output the sum of the values of the removed elements. Specifically, let A_j be the j-th element of the current A and n be the length of A. For p and q such that A_p=x and A_q=y, output A_{\min(p,q)+1} + \dots + A_{\max(p,q)-1} and update A to (A_1,\dots,A_{\min(p,q)},A_{\max(p,q)},\dots,A_n). It is guaranteed that A contains both x and y immediately before processing this query.

Note that for any sequence of queries, the same value never appears multiple times in A during the process of handling queries, and thus the position where a value appears in A is unique (if it exists).

Constraints

• 1\leq Q \leq 5\times 10^5
• For the i-th query:
  • If it is a type 1 query:
    • 0\leq x < i
    • A contains x immediately before processing the query.
  • If it is a type 2 query:
    • 0\leq x < y < i
    • A contains both x and y immediately before processing the query.
• All input values are integers.

Sample Input 1

6
1 0
1 1
1 0
2 2 3
1 2
2 0 5

Sample Output 1

1
5

Initially, A=(0).

• 1st query: Insert 1 immediately after 0. A becomes (0,1).
• 2nd query: Insert 2 immediately after 1. A becomes (0,1,2).
• 3rd query: Insert 3 immediately after 0. A becomes (0,3,1,2).
• 4th query: Remove the elements between 2 and 3, namely 1, and output the sum of the removed values, which is 1. A becomes (0,3,2).
• 5th query: Insert 5 immediately after 2. A becomes (0,3,2,5).
• 6th query: Remove the elements between 0 and 5, namely 3,2, and output the sum of the removed values, which is 5. A becomes (0,5).

Sample Input 2

2
1 0
2 0 1

Sample Output 2

0

In the 2nd query, we remove all elements between 0 and 1, but there are actually no such elements, so no elements are removed and the output value is 0.

Sample Input 3

10
1 0
1 1
2 0 2
2 0 2
1 0
1 5
2 0 5
2 2 6
1 6
1 9

Sample Output 3

1
0
0
0