Problem Statement

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

How many different strings can be obtained by permuting the characters in S?

Constraints

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

Sample Input 1

aba

Sample Output 1

3

By permuting the characters in S= aba, three different strings can be obtained: aab, aba, baa.

Sample Input 2

ccc

Sample Output 2

1

By permuting the characters in S= ccc, just one string can be obtained: ccc.

Sample Input 3

xyz

Sample Output 3

6

By permuting the characters in S= xyz, six different strings can be obtained: xyz, xzy, yxz, yzx, zxy, zyx.

Problem Statement

You are given a tree with N vertices and N-1 edges.
The vertices are numbered 1,2,\ldots,N. The i-th edge connects Vertex a_i and Vertex b_i.

Determine whether this tree is a star.

Here, a star is a tree where there is a vertex directly connected to all other vertices.

Notes

For the definition of a tree, see Tree (graph theory) - Wikipedia.

Constraints

• 3 \leq N \leq 10^5
• 1 \leq a_i \lt b_i \leq N
• The given graph is a tree.

Sample Input 1

5
1 4
2 4
3 4
4 5

Sample Output 1

Yes

The given graph is a star.

Sample Input 2

4
2 4
1 4
2 3

Sample Output 2

No

The given graph is not a star.

Sample Input 3

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

Sample Output 3

Yes

Problem Statement

There is a 10^{100} \times 7 matrix A, where the (i,j)-th entry is (i-1) \times 7 + j for every pair of integers (i,j)\ (1 \leq i \leq 10^{100}, 1 \leq j \leq 7).

Given an N \times M matrix B, determine whether B is some (unrotated) rectangular part of A.

Constraints

• 1 \leq N \leq 10^4
• 1 \leq M \leq 7
• 1 \leq B_{i,j} \leq 10^9
• All values in input are integers.

Sample Input 1

2 3
1 2 3
8 9 10

Sample Output 1

Yes

The given matrix B is the top-left 2 \times 3 submatrix of A.

Sample Input 2

2 1
1
2

Sample Output 2

No

Although the given matrix B would match the top-left 1 \times 2 submatrix of A after rotating 90 degrees, the Problem Statement asks whether B is an unrotated part of A, so the answer is No.

Sample Input 3

10 4
1346 1347 1348 1349
1353 1354 1355 1356
1360 1361 1362 1363
1367 1368 1369 1370
1374 1375 1376 1377
1381 1382 1383 1384
1388 1389 1390 1391
1395 1396 1397 1398
1402 1403 1404 1405
1409 1410 1411 1412

Sample Output 3

Yes

Problem Statement

Takahashi is playing with toy trains, connecting and disconnecting them.
There are N toy train cars, with car numbers: Car 1, Car 2, \ldots, Car N.
Initially, all cars are separated.

You will be given Q queries. Process them in the order they are given. There are three kinds of queries, as follows.

• 1 x y: Connect the front of Car y to the rear of Car x.
  It is guaranteed that:

  • x \neq y
  • just before this query, no train is connected to the rear of Car x;
  • just before this query, no train is connected to the front of Car y;
  • just before this query, Car x and Car y belong to different connected components.

• 2 x y: Disconnect the front of Car y from the rear of Car x.
  It is guaranteed that:

  • x \neq y;
  • just before this query, the front of Car y is directly connected to the rear of Car x.

• 3 x: Print the car numbers of the cars belonging to the connected component containing Car x, from front to back.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• 1 \leq x \leq N
• 1 \leq y \leq N
• All values in input are integers.
• All queries satisfy the conditions in the Problem Statement.
• The queries of the format 3 x ask to print at most 10^6 car numbers in total.

Sample Input 1

7 14
1 6 3
1 4 1
1 5 2
1 2 7
1 3 5
3 2
3 4
3 6
2 3 5
2 4 1
1 1 5
3 2
3 4
3 6

Sample Output 1

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

The figure below shows the cars when the first 5 queries are processed.
For example, Car 2 belongs to the same connected component as Cars 3, 5, 6, 7, which is different from the connected component containing Cars 1, 4.

The figure below shows the cars when the first 11 queries are processed.

Problem Statement

There are N 7's drawn in the first quadrant of a plane.

The i-th 7 is a figure composed of a segment connecting (x_i-1,y_i) and (x_i,y_i), and a segment connecting (x_i,y_i-1) and (x_i,y_i).

You can choose zero or more from the N 7's and delete them.

What is the maximum possible number of 7's that are wholly visible from the origin after the optimal deletion?

Here, the i-th 7 is wholly visible from the origin if and only if:

• the interior (excluding borders) of the quadrilateral whose vertices are the origin, (x_i-1,y_i), (x_i,y_i), (x_i,y_i-1) does not intersect with the other 7's.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq x_i,y_i \leq 10^9
• (x_i,y_i) \neq (x_j,y_j)\ (i \neq j)
• All values in input are integers.

Sample Input 1

3
1 1
2 1
1 2

Sample Output 1

2

If the first 7 is deleted, the other two 7's ― the second and third ones ― will be wholly visible from the origin, which is optimal.

If no 7's are deleted, only the first 7 is wholly visible from the origin.

Sample Input 2

10
414598724 87552841
252911401 309688555
623249116 421714323
605059493 227199170
410455266 373748111
861647548 916369023
527772558 682124751
356101507 249887028
292258775 110762985
850583108 796044319

Sample Output 2

10

It is best to keep all 7's.

Problem Statement

We have N cards. The i-th card has a string S_i written on it.

Find the lexicographically smallest string that can be obtained by choosing K of these cards and concatenating them in any order.

Constraints

• 1 \leq K \leq N \leq 50
• 1 \leq |S_i| \leq 50
• S_i consists of lowercase English letters.

Sample Input 1

4 3
ode
zaaa
r
atc

Sample Output 1

atcoder

Note that it is not possible to reverse or permute the string written on a card.
For example, ode written on the first card cannot be used as edo or deo.

Sample Input 2

5 2
z
z
zzz
z
zzzzzz

Sample Output 2

zz

There may be a pair i, j (i\neq j) such that S_i = S_j.

Problem Statement

We have a grid with H horizontal rows and W vertical columns. Each square contains an integer. The square (i, j) at the i-th row from the top and j-th column from the left contains the integer A_{i,j}.

Takahashi will choose zero or more from the H \times W squares and draw an X on each of them. An X is composed of a segment connecting the top-left and bottom-right corners, and a segment connecting the top-right and bottom-left corners.

Let us define Takahashi's score as (the sum of integers contained in the squares on which X is drawn) - C \times (the minimum number of segments needed to draw the X's).

Here, Takahashi can draw X's on diagonally adjacent squares at once.

For example, he can draw X's on the squares (1, 1) and (2, 2) with three segments:

• a segment connecting the top-left corner of (1, 1) and the bottom-right corner of (2, 2),
• a segment connecting the top-right corner of (1, 1) and the bottom-left corner of (1, 1),
• a segment connecting the top-right corner of (2, 2) and the bottom-left corner of (2, 2).

Find Takahashi's maximum possible score. Note that nothing should be drawn on unchosen squares.

Constraints

• 1 \leq H,W \leq 100
• 1 \leq C \leq 10^9
• 1 \leq A_{i,j} \leq 10^9
• All values in input are integers.

Sample Input 1

2 2 2
2 10
8 3

Sample Output 1

12

If he chooses the squares (1,2) and (2,1), he can draw X's on them with three segments:

• a segment connecting the top-left corner of (1, 2) and the bottom-right corner of (1, 2),
• a segment connecting the top-left corner of (2, 1) and the bottom-right corner of (2, 1),
• a segment connecting the top-right corner of (1, 2) and the bottom-left corner of (2, 1).

Thus, Takahashi's score here will be 10+8-2 \times 3=12.

There is no way to mark squares that achieves a strictly higher score, so the answer is 12.

Sample Input 2

3 3 100
1 1 1
1 1 1
1 1 1

Sample Output 2

0

It is best to mark no squares.

Sample Input 3

8 9 970861213
1313462 943495812 203775264 839015475 115668311 14701110 819458175 827176922 236492592
843915104 786367010 344840288 618248834 824858165 549189141 120648070 805825275 933750119
709330492 38579914 890555497 75314343 238373458 854061807 637519536 53226153 627677130
671706386 380984116 221773266 787763728 639374738 298691145 359138139 183373508 524415106
716502263 150803008 390520954 913021901 553285119 876389099 952721235 46809105 635239775
355621458 511843148 117663063 37274476 891025941 832254337 346436418 783134705 488516288
383723241 322408013 948364423 409068145 120813872 697127655 968230339 988041557 222591780
712959990 233114128 210373172 798667159 568746366 579461421 923556823 777007925 422249456

Sample Output 3

9785518299

Problem Statement

There are N chairs arranged in a row, called Chair 1, Chair 2, \ldots, Chair N.
A chair seats only one person.

M people will sit on M of these chairs. Here, let us define the score as follows:

\displaystyle \prod_{i=1}^{M-1} (B_{i+1} - B_i), where B=(B_1,B_2,\ldots,B_M) is the sorted list of the indices of the chairs the people sit on.

Person i (1 \leq i \leq K) is already sitting on Chair A_i.
There are {} _ {N-K} \mathrm{P} _ {M-K} ways for the other M-K people to take seats. Find the sum of the scores for all of these ways.

Since this sum may be enormous, compute it modulo 998244353.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 2 \leq M \leq N
• 0 \leq K \leq M
• 1 \leq A_1 \lt A_2 \lt \ldots \lt A_K \leq N
• All values in input are integers.

Sample Input 1

5 3 2
1 3

Sample Output 1

7

If Person 3 sits on Chair 2, the score will be (2-1) \times (3-2)=1 \times 1 = 1.
If Person 3 sits on Chair 4, the score will be (3-1) \times (4-3)=2 \times 1 = 2.
If Person 3 sits on Chair 5, the score will be (3-1) \times (5-3)=2 \times 2 = 4.
The answer is 1+2+4=7.

Sample Input 2

6 6 1
4

Sample Output 2

120

The score for every way of sitting will be 1.
There are {} _ {5} \mathrm{P} _ {5} = 120 ways of sitting, so the answer is 120.

Sample Input 3

99 10 3
10 50 90

Sample Output 3

761621047