Problem Statement

Given a length-3 string S consisting of uppercase English letters, print Yes if S equals one of ACE, BDF, CEG, DFA, EGB, FAC, and GBD; print No otherwise.

Constraints

• S is a length-3 string consisting of uppercase English letters.

Sample Input 1

ABC

Sample Output 1

No

When S = ABC, S does not equal any of ACE, BDF, CEG, DFA, EGB, FAC, and GBD, so No should be printed.

Sample Input 2

FAC

Sample Output 2

Yes

Sample Input 3

XYX

Sample Output 3

No

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

There are N sellers and M buyers in an apple market.

The i-th seller may sell an apple for A_i yen or more (yen is the currency in Japan).

The i-th buyer may buy an apple for B_i yen or less.

Find the minimum integer X that satisfies the following condition.

Condition: The number of people who may sell an apple for X yen is greater than or equal to the number of people who may buy an apple for X yen.

Constraints

• 1 \leq N,M \leq 2\times 10^5
• 1\leq A_i,B_i \leq 10^9
• All input values are integers.

Sample Input 1

3 4
110 90 120
100 80 120 10000

Sample Output 1

110

Two sellers, the 1-st and 2-nd, may sell an apple for 110 yen; two buyers, the 3-rd and 4-th, may buy an apple for 110 yen. Thus, 110 satisfies the condition.

Since an integer less than 110 does not satisfy the condition, this is the answer.

Sample Input 2

5 2
100000 100000 100000 100000 100000
100 200

Sample Output 2

201

Sample Input 3

3 2
100 100 100
80 120

Sample Output 3

100

Problem Statement

You are given a non-empty string S consisting of (, ), and ?.
There are 2^x ways to obtain a new string by replacing each ? in S with ( and ), where x is the number of occurrences of ? in S. Among them, find the number, modulo 998244353, of ways that yield a parenthesis string.

A string is said to be a parenthesis string if one of the following conditions is satisfied.

• It is an empty string.
• It is a concatenation of (, A, and ), for some parenthesis string A.
• It is a concatenation of A and B, for some non-empty parenthesis strings A and B.

Constraints

• S is a non-empty string of length at most 3000 consisting of (, ), and ?.

Sample Input 1

(???(?

Sample Output 1

2

Replacing S with ()()() or (())() yields a parenthesis string.
The other replacements do not yield a parenthesis string, so 2 should be printed.

Sample Input 2

)))))

Sample Output 2

0

Sample Input 3

??????????????(????????(??????)?????????(?(??)

Sample Output 3

603032273

Print the count modulo 998244353.

Problem Statement

There are N rectangular cuboids in a three-dimensional space.

These cuboids do not overlap. Formally, for any two different cuboids among them, their intersection has a volume of 0.

The diagonal of the i-th cuboid is a segment that connects two points (X_{i,1},Y_{i,1},Z_{i,1}) and (X_{i,2},Y_{i,2},Z_{i,2}), and its edges are all parallel to one of the coordinate axes.

For each cuboid, find the number of other cuboids that share a face with it.
Formally, for each i, find the number of j with 1\leq j \leq N and j\neq i such that the intersection of the surfaces of the i-th and j-th cuboids has a positive area.

Constraints

• 1 \leq N \leq 10^5
• 0 \leq X_{i,1} < X_{i,2} \leq 100
• 0 \leq Y_{i,1} < Y_{i,2} \leq 100
• 0 \leq Z_{i,1} < Z_{i,2} \leq 100
• Cuboids do not have an intersection with a positive volume.
• All input values are integers.

Sample Input 1

4
0 0 0 1 1 1
0 0 1 1 1 2
1 1 1 2 2 2
3 3 3 4 4 4

Sample Output 1

1
1
0
0

The 1-st and 2-nd cuboids share a rectangle whose diagonal is the segment connecting two points (0,0,1) and (1,1,1).
The 1-st and 3-rd cuboids share a point (1,1,1), but do not share a surface.

Sample Input 2

3
0 0 10 10 10 20
3 4 1 15 6 10
0 9 6 1 20 10

Sample Output 2

2
1
1

Sample Input 3

8
0 0 0 1 1 1
0 0 1 1 1 2
0 1 0 1 2 1
0 1 1 1 2 2
1 0 0 2 1 1
1 0 1 2 1 2
1 1 0 2 2 1
1 1 1 2 2 2

Sample Output 3

3
3
3
3
3
3
3
3

Problem Statement

There are N items.
Each of these is one of a pull-tab can, a regular can, or a can opener.
The i-th item is described by an integer pair (T_i, X_i) as follows:

• If T_i = 0, the i-th item is a pull-tab can; if you obtain it, you get a happiness of X_i.
• If T_i = 1, the i-th item is a regular can; if you obtain it and use a can opener against it, you get a happiness of X_i.
• If T_i = 2, the i-th item is a can opener; it can be used against at most X_i cans.

Find the maximum total happiness that you get by obtaining M items out of N.

Constraints

• 1 \leq M \leq N \leq 2 \times 10^5
• T_i is 0, 1, or 2.
• 1 \leq X_i \leq 10^9
• All input values are integers.

Sample Input 1

8 4
0 6
0 6
1 3
1 5
1 15
2 1
2 10
2 100

Sample Output 1

27

If you obtain the 1-st, 2-nd, 5-th, and 7-th items, and use the 7-th item (a can opener) against the 5-th item, you will get a happiness of 6 + 6 + 15 = 27.
There are no ways to obtain items to get a happiness of 28 or greater, but you can still get a happiness of 27 by obtaining the 6-th or 8-th items instead of the 7-th in the combination above.

Sample Input 2

5 5
1 5
1 5
1 5
1 5
1 5

Sample Output 2

0

Sample Input 3

12 6
2 2
0 1
0 9
1 3
1 5
1 3
0 4
2 1
1 8
2 1
0 1
0 4

Sample Output 3

30

Problem Statement

You are given a tree with N vertices. The vertices are numbered from 1 through N, and the i-th edge connects vertex A_i and vertex B_i.
Find the number of tuples of integers (i,j,k) such that:

• 1 \leq i < j < k \leq N; and
• the given tree does not contain a simple path that contains all of vertices i, j, and k.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq N
• The given graph is a tree.
• All input values are integers.

Sample Input 1

5
1 2
2 3
2 4
1 5

Sample Output 1

2

Two tuples satisfy the conditions: (i,j,k) = (1,3,4),(3,4,5).

Sample Input 2

6
1 2
2 3
3 4
4 5
5 6

Sample Output 2

0

Sample Input 3

12
1 6
3 4
10 4
5 9
3 1
2 3
7 2
2 12
1 5
6 8
4 11

Sample Output 3

91

Problem Statement

Takahashi is going to decide nicknames of N people, person 1,\ldots,N.

Person i wants a nickname S_i. To avoid giving the same nickname to multiple people, he is going to decide their nicknames as follows:

• For each i=1,\ldots,N in order, decide person i's nickname as follows:
  • Initialize a variable k_i with 1.
  • Repeatedly increment k_i by one while the k_i-time repetition of S_i is someone's nickname.
  • Let person i's nickname be the k_i-time repetition of S_i.

Find k_1,\ldots, and k_N after deciding nicknames of the N people.

Constraints

• N \geq 1
• S_i is a string of length at least 1 consisting of lowercase English letters.
• The sum of lengths of S_i is at most 2\times 10^5.

Sample Input 1

3
snuke
snuke
rng

Sample Output 1

1 2 1

• First, he decides person 1's nickname.
  • Let k_1=1.
  • The k_1-time repetition of S_1 is snuke, which is nobody's nickname, so person 1's nickname is set to snuke.
• Next, he decides person 2's nickname.
  • Let k_2=1.
  • The k_2-time repetition of S_2 is snuke, which is already a nickname of person 1, so increment k_2 by one to make it 2.
  • The k_2-time repetition of S_2 is snukesnuke, which is nobody's nickname, so person 2's nickname is set to snukesnuke.
• Finally, he decides person 3's nickname.
  • Let k_3=1.
  • The k_3-time repetition of S_3 is rng, which is nobody's nickname, so person 3's nickname is set to rng.

Thus, k_1, k_2, and k_3 result in 1, 2, and 1, respectively.

Sample Input 2

4
aa
a
a
aaa

Sample Output 2

1 1 3 2

• Person 1's nickname is set to aa.
• Person 2's nickname is set to a.
• Person 3's nickname is set to aaa, because a and aa are already nicknames of someone else.
• Person 4's nickname is set to aaaaaa, because aaa is already a nickname of someone else.

Sample Input 3

5
x
x
x
x
x

Sample Output 3

1 2 3 4 5