Problem Statement

N people labeled 1,2,\dots,N took an exam, and person i scored A_i points.
Only those who scored at least L points pass this exam.
Determine how many people out of the N have passed the exam.

Constraints

• All input values are integers.
• 1 \le N \le 100
• 1 \le L \le 1000
• 0 \le A_i \le 1000

Sample Input 1

5 60
60 20 100 90 40

Sample Output 1

3

Five people took the exam. You need to score at least 60 points to pass.

• Person 1 scored 60 points, so they passed.
• Person 2 scored 20 points, so they did not pass.
• Person 3 scored 100 points, so they passed.
• Person 4 scored 90 points, so they passed.
• Person 5 scored 40 points, so they did not pass.

From the above, we can see that three people have passed.

Sample Input 2

4 80
79 78 77 76

Sample Output 2

0

There may be cases no one has passed.

Sample Input 3

10 50
31 41 59 26 53 58 97 93 23 84

Sample Output 3

6

Problem Statement

In the ceremony commemorating ABC400, we want to arrange 400 people in a rectangular formation of A rows and B columns without any gaps.

You are given a positive integer A. Print the value of a positive integer B for which such an arrangement is possible. If there is no such positive integer B, print -1.

Constraints

• A is an integer between 1 and 400, inclusive.

Sample Input 1

10

Sample Output 1

40

We can arrange 400 people in 10 rows and 40 columns.

Sample Input 2

11

Sample Output 2

-1

Sample Input 3

400

Sample Output 3

1

Problem Statement

There are N people, and the current hair length of the i-th person (1 \leq i \leq N) is L_i.
Each person's hair grows by 1 per day.

Print the number of days after which the number of people whose hair length is at least T becomes P or more for the first time.
If there are already P or more people whose hair length is at least T now, print 0.

Constraints

• 1 \leq N \leq 100
• 1 \leq L_i \leq 100
• 1 \leq T \leq 100
• 1 \leq P \leq N
• All input values are integers.

Sample Input 1

5 10 3
3 11 1 6 2

Sample Output 1

7

There are five people, and their current hair lengths are 3, 11, 1, 6, 2, so there is one person whose hair length is at least 10.

After seven days, the hair lengths of the people will be 10, 18, 8, 13, 9, respectively, and there will be three people whose hair length is at least 10.
After six days, there are only two people whose hair length is at least 10, not satisfying the condition, so print 7.

Sample Input 2

2 5 2
10 10

Sample Output 2

0

Since there are already two people whose hair length is at least 5 now, satisfying the condition, so print 0.

Sample Input 3

3 10 1
1 2 3

Sample Output 3

7

Problem Statement

Takahashi invented Tak Code, a two-dimensional code. A TaK Code satisfies all of the following conditions:

• It is a region consisting of nine horizontal rows and nine vertical columns.
• All the 18 cells in the top-left and bottom-right three-by-three regions are black.
• All the 14 cells that are adjacent (horizontally, vertically, or diagonally) to the top-left or bottom-right three-by-three region are white.

It is not allowed to rotate a TaK Code.

You are given a grid with N horizontal rows and M vertical columns. The state of the grid is described by N strings, S_1,\ldots, and S_N, each of length M. The cell at the i-th row from the top and j-th column from the left is black if the j-th character of S_i is #, and white if it is ..

Find all the nine-by-nine regions, completely contained in the grid, that satisfy the conditions of a TaK Code.

Constraints

• 9 \leq N,M \leq 100
• N and M are integers.
• S_i is a string of length M consisting of . and #.

Sample Input 1

19 18
###......###......
###......###......
###..#...###..#...
..............#...
..................
..................
......###......###
......###......###
......###......###
.###..............
.###......##......
.###..............
............###...
...##.......###...
...##.......###...
.......###........
.......###........
.......###........
........#.........

Sample Output 1

1 1
1 10
7 7
10 2

A TaK Code looks like the following, where # is a black cell, . is a white cell, and ? can be either black or white.

###.?????
###.?????
###.?????
....?????
?????????
?????....
?????.###
?????.###
?????.###

In the grid given by the input, the nine-by-nine region, whose top-left cell is at the 10-th row from the top and 2-nd column from the left, satisfies the conditions of a TaK Code, as shown below.

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

Sample Input 2

9 21
###.#...........#.###
###.#...........#.###
###.#...........#.###
....#...........#....
#########...#########
....#...........#....
....#.###...###.#....
....#.###...###.#....
....#.###...###.#....

Sample Output 2

1 1

Sample Input 3

18 18
######............
######............
######............
######............
######............
######............
..................
..................
..................
..................
..................
..................
............######
............######
............######
............######
............######
............######

Sample Output 3

There may be no region that satisfies the conditions of TaK Code.

Problem Statement

In the xy-plane, we have N points numbered 1 through N.
Point i is at the coordinates (X_i,Y_i). Any two different points are at different positions.
Find the number of ways to choose three of these N points so that connecting the chosen points with segments results in a triangle with a positive area.

Constraints

• All values in input are integers.
• 3 \le N \le 300
• -10^9 \le X_i,Y_i \le 10^9
• (X_i,Y_i) \neq (X_j,Y_j) if i \neq j.

Sample Input 1

4
0 1
1 3
1 1
-1 -1

Sample Output 1

3

The figure below illustrates the points.

There are three ways to choose points that form a triangle: \{1,2,3\},\{1,3,4\},\{2,3,4\}.

Sample Input 2

20
224 433
987654321 987654321
2 0
6 4
314159265 358979323
0 0
-123456789 123456789
-1000000000 1000000000
124 233
9 -6
-4 0
9 5
-7 3
333333333 -333333333
-9 -1
7 -10
-1 5
324 633
1000000000 -1000000000
20 0

Sample Output 2

1124

Problem Statement

AtCoder Inc. sells T-shirts with its logo.

You are given Takahashi's schedule for N days as a string S of length N consisting of 0, 1, and 2.
Specifically, for an integer i satisfying 1\leq i\leq N,

• if the i-th character of S is 0, he has no plan scheduled for the i-th day;
• if the i-th character of S is 1, he plans to go out for a meal on the i-th day;
• if the i-th character of S is 2, he plans to attend a competitive programming event on the i-th day.

Takahashi has M plain T-shirts, all washed and ready to wear just before the first day.
In addition, to be able to satisfy the following conditions, he will buy several AtCoder logo T-shirts.

• On days he goes out for a meal, he will wear a plain or logo T-shirt.
• On days he attends a competitive programming event, he will wear a logo T-shirt.
• On days with no plans, he will not wear any T-shirts. Also, he will wash all T-shirts worn at that point. He can wear them again from the next day onwards.
• Once he wears a T-shirt, he cannot wear it again until he washes it.

Determine the minimum number of T-shirts he needs to buy to be able to wear appropriate T-shirts on all scheduled days during the N days. If he does not need to buy new T-shirts, print 0.
Assume that the purchased T-shirts are also washed and ready to use just before the first day.

Constraints

• 1\leq M\leq N\leq 1000
• S is a string of length N consisting of 0, 1, and 2.
• N and M are integers.

Sample Input 1

6 1
112022

Sample Output 1

2

If Takahashi buys two logo T-shirts, he can wear T-shirts as follows:

• On the first day, he wears a logo T-shirt to go out for a meal.
• On the second day, he wears a plain T-shirt to go out for a meal.
• On the third day, he wears a logo T-shirt to attend a competitive programming event.
• On the fourth day, he has no plans, so he washes all the worn T-shirts. This allows him to reuse the T-shirts worn on the first, second, and third days.
• On the fifth day, he wears a logo T-shirt to attend a competitive programming event.
• On the sixth day, he wears a logo T-shirt to attend a competitive programming event.

If he buys one or fewer logo T-shirts, he cannot use T-shirts to meet the conditions no matter what. Hence, print 2.

Sample Input 2

3 1
222

Sample Output 2

3

Sample Input 3

2 1
01

Sample Output 3

0

He does not need to buy new T-shirts.

Problem Statement

We have a string S. Initially, S= 1.
Process Q queries in the following formats in order.

• 1 x : Append a digit x at the end of S.
• 2 : Delete the digit at the beginning of S.
• 3 : Print the number represented by S in decimal, modulo 998244353.

Constraints

• 1 \leq Q \leq 6 \times 10^5
• For each query in the first format, x \in \{1,2,3,4,5,6,7,8,9\}.
• A query in the second format is given only if S has a length of 2 or greater.
• There is at least one query in the third format.

Sample Input 1

3
3
1 2
3

Sample Output 1

1
12

In the first query, S is 1, so you should print 1 modulo 998244353, that is, 1.
In the second query, S becomes 12.
In the third query, S is 12, so you should print 12 modulo 998244353, that is, 12.

Sample Input 2

3
1 5
2
3

Sample Output 2

5

Sample Input 3

11
1 9
1 9
1 8
1 2
1 4
1 4
1 3
1 5
1 3
2
3

Sample Output 3

0

Be sure to print numbers modulo 998244353.

Problem Statement

You are given a length-N sequence A=(A_1,A_2,\dots,A_N) consisting of 0, 1, and 2, and a length-N string S=S_1S_2\dots S_N consisting of M, E, and X.

Find the sum of \text{mex}(A_i,A_j,A_k) over all tuples of integers (i,j,k) such that 1 \leq i < j < k \leq N and S_iS_jS_k= MEX. Here, \text{mex}(A_i,A_j,A_k) denotes the minimum non-negative integer that equals neither A_i,A_j, nor A_k.

Constraints

• 3\leq N \leq 2\times 10^5
• N is an integer.
• A_i \in \lbrace 0,1,2\rbrace
• S is a string of length N consisting of M, E, and X.

Sample Input 1

4
1 1 0 2
MEEX

Sample Output 1

3

The tuples (i,j,k)\ (1 \leq i < j < k \leq N) such that S_iS_jS_k = MEX are the following two: (i,j,k)=(1,2,4),(1,3,4). Since \text{mex}(A_1,A_2,A_4)=\text{mex}(1,1,2)=0 and \text{mex}(A_1,A_3,A_4)=\text{mex}(1,0,2)=3, the answer is 0+3=3.

Sample Input 2

3
0 0 0
XXX

Sample Output 2

0

Sample Input 3

15
1 1 2 0 0 2 0 2 0 0 0 0 0 2 2
EXMMXXXEMEXEXMM

Sample Output 3

13

Problem Statement

Given is a sequence A of length N. You can do this operation any number of times: when the length of the sequence is at least 2, choose two adjacent values, delete them, and insert their sum where they were. How many sequences can result from zero or more operations? Find the count modulo 998244353.

Constraints

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

Sample Input 1

3
1 -1 1

Sample Output 1

4

The following four sequences can result from zero or more operations.

• {1,-1,1}
• {1,0}
• {0,1}
• {1}

Sample Input 2

10
377914575 -275478149 0 -444175904 719654053 -254224494 -123690081 377914575 -254224494 -21253655

Sample Output 2

321