Problem Statement

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

Here, we define the number of dots in a lowercase English letter as follows:

• If the lowercase English letter is i or j: 1 dot
• If the lowercase English letter is neither i nor j: 0 dots

Find the sum of the numbers of dots over all characters in S.

Constraints

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

Sample Input 1

aiiaj

Sample Output 1

3

The numbers of dots in a, i, i, a, j are 0, 1, 1, 0, 1, respectively.

We have 0 + 1 + 1 + 0 + 1 = 3, so print 3.

Sample Input 2

abcedfgh

Sample Output 2

0

Sample Input 3

jjjjjj

Sample Output 3

6

Problem Statement

Takahashi has a music player. Initially, the volume is 0 and the music is stopped.

From now on, Q operations will be performed in order. The i-th operation is represented by an integer A_i, which means the following:

• If A_i = 1, increase the volume by 1.
• If A_i = 2, if the current volume is 1 or more, decrease it by 1; if it is 0, do nothing.
• If A_i = 3, if the music is stopped, play it; if the music is playing, stop it.

For i = 1, 2, \ldots, Q, solve the following problem:

• Determine whether the music is playing at volume 3 or more immediately after the i-th operation.

Constraints

• 1 \leq Q \leq 2 \times 10^5
• A_i \in \lbrace 1, 2, 3 \rbrace
• All input values are integers.

Sample Input 1

10
2
1
3
1
3
1
1
3
2
2

Sample Output 1

No
No
No
No
No
No
No
Yes
Yes
No

• After the 1-st operation, the volume is 0 and the music is stopped.

• After the 2-nd operation, the volume is 1 and the music is stopped.

• After the 3-rd operation, the volume is 1 and the music is playing.

• After the 4-th operation, the volume is 2 and the music is playing.

• After the 5-th operation, the volume is 2 and the music is stopped.

• After the 6-th operation, the volume is 3 and the music is stopped.

• After the 7-th operation, the volume is 4 and the music is stopped.

• After the 8-th operation, the volume is 4 and the music is playing.

• After the 9-th operation, the volume is 3 and the music is playing.

• After the 10-th operation, the volume is 2 and the music is playing.

Problem Statement

There are N researchers, numbered 1, 2, \ldots, N.

There are M conflicts of interest among the researchers; for i = 1, 2, \ldots, M, researchers A_i and B_i have a conflict of interest with each other.

The reviewers of a paper must be three distinct researchers who are different from the author of the paper and have no conflict of interest with the author.

For i = 1, 2, \ldots, N, solve the following problem:

• Find the number of possible triples of reviewers for a paper authored by researcher i.

Assume that all papers are single-authored.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq N
• A_i \neq B_i
• (A_i, B_i) \neq (A_j, B_j) if i \neq j.
• (A_i, B_i) \neq (B_j, A_j) if i \neq j.
• All input values are integers.

Sample Input 1

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

Sample Output 1

0 1 0 4 4 10

Below, we represent a set of researchers by the set of their numbers.

• There are no possible triples of reviewers for a paper authored by researcher 1.

• The possible triple of reviewers for a paper authored by researcher 2 is \lbrace 4, 5, 6 \rbrace, which is 1 triple.

• There are no possible triples of reviewers for a paper authored by researcher 3.

• The possible triples of reviewers for a paper authored by researcher 4 are \lbrace 2, 3, 5 \rbrace, \lbrace 2, 3, 6 \rbrace, \lbrace 2, 5, 6 \rbrace, \lbrace 3, 5, 6 \rbrace, which is 4 triples.

• The possible triples of reviewers for a paper authored by researcher 5 are \lbrace 1, 2, 4 \rbrace, \lbrace 1, 2, 6 \rbrace, \lbrace 1, 4, 6 \rbrace, \lbrace 2, 4, 6 \rbrace, which is 4 triples.

• The possible triples of reviewers for a paper authored by researcher 6 are \lbrace 1, 2, 3 \rbrace, \lbrace 1, 2, 4 \rbrace, \lbrace 1, 2, 5 \rbrace, \lbrace 1, 3, 4 \rbrace, \lbrace 1, 3, 5 \rbrace, \lbrace 1, 4, 5 \rbrace, \lbrace 2, 3, 4 \rbrace, \lbrace 2, 3, 5 \rbrace, \lbrace 2, 4, 5 \rbrace, \lbrace 3, 4, 5 \rbrace, which is 10 triples.

Sample Input 2

7 3
1 2
3 4
5 6

Sample Output 2

10 10 10 10 10 10 20

Sample Input 3

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

Sample Output 3

1 0 0 1 0 1

Problem Statement

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

Process Q queries in order. Each query is in one of the following formats:

• 1 x : Swap the values of A_x and A_{x+1}.
• 2 l r : Find the value of \displaystyle \sum_{l\leq i\leq r} A_i.

Constraints

• 2\leq N \leq 2\times 10^5
• 1\leq Q \leq 5\times 10^5
• 1\leq A_i \leq 10^4
• For queries of the first type, 1\leq x \leq N-1.
• For queries of the second type, 1\leq l\leq r \leq N.
• All input values are integers.

Sample Input 1

4 4
2 7 1 8
1 2
2 1 2
1 1
2 2 4

Sample Output 1

3
17

• In the 1-st query, swap the values of A_2 and A_3. This makes A=(2,1,7,8).
• In the 2-nd query, find the value of A_1+A_2. The answer is 2+1=3.
• In the 3-rd query, swap the values of A_1 and A_2. This makes A=(1,2,7,8).
• In the 4-th query, find the value of A_2+A_3+A_4. The answer is 2+7+8=17.

Sample Input 2

8 10
22 75 26 45 72 81 47 29
2 2 7
2 6 8
2 4 4
1 2
2 1 3
1 1
2 2 4
1 2
1 4
2 1 1

Sample Output 2

346
157
45
123
142
26

Problem Statement

There are N monsters on a two-dimensional plane. The monsters are numbered from 1 to N, and the coordinates of monster i are (X_i,Y_i). Here, (X_i,Y_i) \neq (0,0). (Each monster can be regarded as a stationary point. That is, monsters have no size.)

Takahashi is standing at the origin of this plane. A powerful laser is always emitted from his eyes, instantly destroying monsters in the direction he is facing. If multiple monsters exist in the direction he is facing, all of them are instantly destroyed.

Aoki is conducting Q independent thought experiments. The j-th thought experiment is as follows:

• Initially, Takahashi is facing the direction toward monster A_j. From now on, Takahashi will rotate clockwise and stop the moment he faces the direction toward monster B_j. Here, how many monsters in total (including monsters A_j and B_j) will be destroyed? If monsters A_j and B_j exist in the same direction from the origin, Takahashi does not rotate at all.

Find the answer to each thought experiment.

Constraints

• 2\leq N \leq 2\times 10^5
• 1\leq Q \leq 2\times 10^5
• -10^9\leq X_i,Y_i \leq 10^9
• (X_i,Y_i)\neq (0,0)
• 1\leq A_j,B_j\leq N
• A_j\neq B_j
• All input values are integers.

Sample Input 1

5 4
0 1
1 -2
1 0
-2 0
3 0
4 1
1 4
5 4
3 5

Sample Output 1

2
5
4
2

• 1-st thought experiment: Initially, Takahashi is facing the direction toward monster 4 (at this time, monster 4 is destroyed). From here, he continues to rotate clockwise and stops the moment he faces the direction toward monster 1 (at this time, monster 1 is destroyed). Since he does not face the direction toward any other monsters, the answer is 2.
• 2-nd thought experiment: Initially, Takahashi is facing the direction toward monster 1 (at this time, monster 1 is destroyed). From here, as he continues to rotate clockwise, he faces the direction toward monsters 3 and 5 along the way, so they are destroyed. As he continues to rotate further, he faces the direction toward monster 2 along the way, so it is destroyed. Finally, he stops the moment he faces the direction toward monster 4 (at this time, monster 4 is destroyed). Therefore, the answer is 5.
• 3-rd thought experiment: Monsters 3, 5, 2, 4 are destroyed, so the answer is 4.
• 4-th thought experiment: Monsters 3, 5 are destroyed, so the answer is 2. Note that since monsters 3 and 5 exist in the same direction from the origin, Takahashi does not rotate at all.

Sample Input 2

2 1
1 2
1 2
1 2

Sample Output 2

2

Multiple monsters may exist at the same coordinates.

Sample Input 3

8 10
-84 -60
-100 8
77 55
-14 -10
50 -4
-63 -45
26 -17
-7 -5
3 7
2 4
8 4
8 4
7 1
1 7
6 3
4 7
4 5
2 6

Sample Output 3

3
8
4
4
5
8
6
8
7
8

Problem Statement

There is a grid with N rows and N columns. The square at the i-th row from the top and j-th column from the left is denoted as square (i, j).

Each square in the grid is painted white or black. The information of the grid is given by N strings S_1, S_2, \ldots, S_N. If the j-th character of S_i is ., square (i, j) is painted white; if the j-th character of S_i is #, square (i, j) is painted black.

You will repaint some squares so that both of the following conditions are satisfied:

• For every row, the following condition holds:
  • There exists an integer k satisfying 0 \leq k \leq N such that the leftmost k squares of that row are painted white and the other squares are painted black.
• For every column, the following condition holds:
  • There exists an integer k satisfying 0 \leq k \leq N such that the topmost k squares of that column are painted white and the other squares are painted black.

Find the minimum number of squares that need to be repainted to satisfy the conditions.

Constraints

• 1 \leq N \leq 5000
• N is an integer.
• S_i is a string of length N consisting of . and #.

Sample Input 1

3
..#
#.#
.#.

Sample Output 1

2

You can satisfy the conditions by repainting square (2, 1) white and square (3, 3) black.

Sample Input 2

5
..#.#
#..##
###.#
.###.
#....

Sample Output 2

9

Problem Statement

There are N types of items. The i-th type of item has weight W_i and value V_i, and you have K_i of them.

When choosing some (possibly zero) items from these K_1+\dots+K_N items so that the total weight does not exceed C, find the maximum possible total value of the chosen items.

Constraints

• 1\leq N \leq 2\times 10^5
• 1\leq C \leq 2\times 10^9
• 1\leq W_i \leq 3
• 1\leq V_i \leq 10^9
• 1\leq K_i \leq 10^9
• All input values are integers.

Sample Input 1

4 7
3 5 5
1 2 4
2 7 1
2 1 2

Sample Output 1

16

If you choose 1 item of the 1-st type, 2 items of the 2-nd type, and 1 item of the 3-rd type, the total weight is 3\times 1+1\times 2+2\times 1=7\ (\leq C) and the total value is 5\times 1+2\times 2+7\times 1=16, which is the maximum.

Sample Input 2

2 1
3 442 442
2 442 442

Sample Output 2

0

You cannot choose any items.

Sample Input 3

15 913575467
1 60505998 818008580
2 121011861 138996221
3 181517958 501899080
1 60506027 840594328
3 181517875 350034067
1 60505924 155374934
3 181517816 910748511
1 60506042 545531545
3 181517877 797829355
3 181517837 164163676
1 60505894 353195922
1 60505912 954291757
1 60506022 160449218
3 181517873 404011431
1 60506043 782177068

Sample Output 3

55276836358648682