Problem Statement

Takahashi set task goals for N days.

He aimed to complete A_i tasks on day i (1 \leq i \leq N), and actually completed B_i tasks.

Find the number of days when he completed more tasks than his goal.

Constraints

• 1 \leq N \leq 100
• 1 \leq A_i, B_i \leq 100
• All input values are integers.

Sample Input 1

4
2 8
5 5
5 4
6 7

Sample Output 1

2

Takahashi completed more tasks than his goal on the 1st and 4th days.

Sample Input 2

5
1 1
1 1
1 1
1 1
1 1

Sample Output 2

0

Sample Input 3

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

Sample Output 3

3

Problem Statement

In AtCoder, the top 10 rated players' usernames are displayed with a gold crown, and the top-rated player's username is displayed with a platinum crown.

At the start of this contest, the usernames and ratings of the top 10 rated players in the algorithm category are as follows:

tourist 3858
ksun48 3679
Benq 3658
Um_nik 3648
apiad 3638
Stonefeang 3630
ecnerwala 3613
mnbvmar 3555
newbiedmy 3516
semiexp 3481

You are given the username S of one of these players. Print that player's rating.

Constraints

• S is equal to one of the usernames of the top 10 rated players in the algorithm category.

Sample Input 1

tourist

Sample Output 1

3858

At the start of this contest, the rating of tourist in the algorithm category is 3858.

Sample Input 2

semiexp

Sample Output 2

3481

At the start of this contest, the rating of semiexp in the algorithm category is 3481.

Problem Statement

There is a grid with H rows and W columns; initially, all cells are painted white. Let (i, j) denote the cell at the i-th row from the top and the j-th column from the left.

This grid is considered to be toroidal. That is, (i, 1) is to the right of (i, W) for each 1 \leq i \leq H, and (1, j) is below (H, j) for each 1 \leq j \leq W.

Takahashi is at (1, 1) and facing upwards. Print the color of each cell in the grid after Takahashi repeats the following operation N times.

• If the current cell is painted white, repaint it black, rotate 90^\circ clockwise, and move forward one cell in the direction he is facing. Otherwise, repaint the current cell white, rotate 90^\circ counterclockwise, and move forward one cell in the direction he is facing.

Constraints

• 1 \leq H, W \leq 100
• 1 \leq N \leq 1000
• All input values are integers.

Sample Input 1

3 4 5

Sample Output 1

.#..
##..
....

The cells of the grid change as follows due to the operations:

....   #...   ##..   ##..   ##..   .#..
.... → .... → .... → .#.. → ##.. → ##..
....   ....   ....   ....   ....   ....

Sample Input 2

2 2 1000

Sample Output 2

..
..

Sample Input 3

10 10 10

Sample Output 3

##........
##........
..........
..........
..........
..........
..........
..........
..........
#........#

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

There are zero or more sensors placed on a grid of H rows and W columns. Let (i, j) denote the square in the i-th row from the top and the j-th column from the left.
Whether each square contains a sensor is given by the strings S_1, S_2, \ldots, S_H, each of length W. (i, j) contains a sensor if and only if the j-th character of S_i is #.
These sensors interact with other sensors in the squares horizontally, vertically, or diagonally adjacent to them and operate as one sensor. Here, a cell (x, y) and a cell (x', y') are said to be horizontally, vertically, or diagonally adjacent if and only if \max(|x-x'|,|y-y'|) = 1.
Note that if sensor A interacts with sensor B and sensor A interacts with sensor C, then sensor B and sensor C also interact.

Considering the interacting sensors as one sensor, find the number of sensors on this grid.

Constraints

• 1 \leq H, W \leq 1000
• H and W are integers.
• S_i is a string of length W where each character is # or ..

Sample Input 1

5 6
.##...
...#..
....##
#.#...
..#...

Sample Output 1

3

When considering the interacting sensors as one sensor, the following three sensors exist:

• The interacting sensors at (1,2),(1,3),(2,4),(3,5),(3,6)
• The sensor at (4,1)
• The interacting sensors at (4,3),(5,3)

Sample Input 2

3 3
#.#
.#.
#.#

Sample Output 2

1

Sample Input 3

4 2
..
..
..
..

Sample Output 3

0

Sample Input 4

5 47
.#..#..#####..#...#..#####..#...#...###...#####
.#.#...#.......#.#...#......##..#..#...#..#....
.##....#####....#....#####..#.#.#..#......#####
.#.#...#........#....#......#..##..#...#..#....
.#..#..#####....#....#####..#...#...###...#####

Sample Output 4

7

Problem Statement

We have a sequence of N numbers: A = (a_1, a_2, \dots, a_N).
Process the Q queries explained below.

• Query i: You are given a pair of integers (x_i, k_i). Let us look at the elements of A one by one from the beginning: a_1, a_2, \dots Which element will be the k_i-th occurrence of the number x_i?
  Print the index of that element, or -1 if there is no such element.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq a_i \leq 10^9 (1 \leq i \leq N)
• 0 \leq x_i \leq 10^9 (1 \leq i \leq Q)
• 1 \leq k_i \leq N (1 \leq i \leq Q)
• All values in input are integers.

Sample Input 1

6 8
1 1 2 3 1 2
1 1
1 2
1 3
1 4
2 1
2 2
2 3
4 1

Sample Output 1

1
2
5
-1
3
6
-1
-1

1 occurs in A at a_1, a_2, a_5. Thus, the answers to Query 1 through 4 are 1, 2, 5, -1 in this order.

Sample Input 2

3 2
0 1000000000 999999999
1000000000 1
123456789 1

Sample Output 2

2
-1

Problem Statement

You are given a sequence of length N: A=(A_1,A_2,\ldots,A_N).
Find the number of triples (i,j,k) that satisfy both of the following conditions.

• 1\leq i \lt j \lt k \leq N
• A_i, A_j, and A_k are distinct.

Constraints

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

Sample Input 1

4
3 1 4 1

Sample Output 1

2

The two triples (i,j,k) satisfying the conditions are (1,2,3) and (1,3,4).

Sample Input 2

10
99999 99998 99997 99996 99995 99994 99993 99992 99991 99990

Sample Output 2

120

Sample Input 3

15
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9

Sample Output 3

355

Problem Statement

We have a tree with 2^N-1 vertices.
The vertices are numbered 1 through 2^N-1. For each 1\leq i < 2^{N-1}, the following edges exist:

• an undirected edge connecting Vertex i and Vertex 2i,
• an undirected edge connecting Vertex i and Vertex 2i+1.

There is no other edge.

Let the distance between two vertices be the number of edges in the simple path connecting those two vertices.

Find the number, modulo 998244353, of pairs of vertices (i, j) such that the distance between them is D.

Constraints

• 2 \leq N \leq 10^6
• 1 \leq D \leq 2\times 10^6
• All values in input are integers.

Sample Input 1

3 2

Sample Output 1

14

The following figure describes the given tree.

There are 14 pairs of vertices such that the distance between them is 2: (1,4),(1,5),(1,6),(1,7),(2,3),(3,2),(4,1),(4,5),(5,1),(5,4),(6,1),(6,7),(7,1),(7,6).

Sample Input 2

14142 17320

Sample Output 2

11284501

Problem Statement

The Republic of Atcoder has N towns numbered 1 through N, and M highways numbered 1 through M.
Highway i connects Town A_i and Town B_i bidirectionally.

King Takahashi is going to construct (N-M-1) new highways so that the following two conditions are satisfied:

• One can travel between every pair of towns using some number of highways
• For each i=1,\ldots,N, exactly D_i highways are directly connected to Town i

Determine if there is such a way of construction. If it exists, print one.

Constraints

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

Sample Input 1

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

Sample Output 1

6 2
5 6
4 5

As in the Sample Output, the conditions can be satisfied by constructing highways connecting Towns 6 and 2, Towns 5 and 6, and Towns 4 and 5, respectively.

Another example to satisfy the conditions is to construct highways connecting Towns 6 and 4, Towns 5 and 6, and Towns 2 and 5, respectively.

Sample Input 2

5 1
1 1 1 1 4
2 3

Sample Output 2

-1

Sample Input 3

4 0
3 3 3 3

Sample Output 3

-1