Problem Statement

Takahashi has two sheets A and B, each composed of black squares and transparent squares, and an infinitely large sheet C composed of transparent squares.
There is also an ideal sheet X for Takahashi composed of black squares and transparent squares.

The sizes of sheets A, B, and X are H_A rows \times W_A columns, H_B rows \times W_B columns, and H_X rows \times W_X columns, respectively.
The squares of sheet A are represented by H_A strings of length W_A, A_1, A_2, \ldots, A_{H_A} consisting of . and #.
If the j-th character (1\leq j\leq W_A) of A_i (1\leq i\leq H_A) is ., the square at the i-th row from the top and j-th column from the left is transparent; if it is #, that square is black.
Similarly, the squares of sheets B and X are represented by H_B strings of length W_B, B_1, B_2, \ldots, B_{H_B}, and H_X strings of length W_X, X_1, X_2, \ldots, X_{H_X}, respectively.

Takahashi's goal is to create sheet X using all black squares in sheets A and B by following the steps below with sheets A, B, and C.

1. Paste sheets A and B onto sheet C along the grid. Each sheet can be pasted anywhere by translating it, but it cannot be cut or rotated.
2. Cut out an H_X\times W_X area from sheet C along the grid. Here, a square of the cut-out sheet will be black if a black square of sheet A or B is pasted there, and transparent otherwise.

Determine whether Takahashi can achieve his goal by appropriately choosing the positions where the sheets are pasted and the area to cut out, that is, whether he can satisfy both of the following conditions.

• The cut-out sheet includes all black squares of sheets A and B. The black squares of sheets A and B may overlap on the cut-out sheet.
• The cut-out sheet coincides sheet X without rotating or flipping.

Constraints

• 1\leq H_A, W_A, H_B, W_B, H_X, W_X\leq 10
• H_A, W_A, H_B, W_B, H_X, W_X are integers.
• A_i is a string of length W_A consisting of . and #.
• B_i is a string of length W_B consisting of . and #.
• X_i is a string of length W_X consisting of . and #.
• Sheets A, B, and X each contain at least one black square.

Sample Input 1

3 5
#.#..
.....
.#...
2 2
#.
.#
5 3
...
#.#
.#.
.#.
...

Sample Output 1

Yes

First, paste sheet A onto sheet C, as shown in the figure below.

     \vdots
  .......  
  .#.#...  
\cdots.......\cdots
  ..#....  
  .......  
     \vdots

Next, paste sheet B so that its top-left corner aligns with that of sheet A, as shown in the figure below.

     \vdots
  .......  
  .#.#...  
\cdots..#....\cdots
  ..#....  
  .......  
     \vdots

Now, cut out a 5\times 3 area with the square in the first row and second column of the range illustrated above as the top-left corner, as shown in the figure below.

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

This includes all black squares of sheets A and B and matches sheet X, satisfying the conditions.

Therefore, print Yes.

Sample Input 2

2 2
#.
.#
2 2
#.
.#
2 2
##
##

Sample Output 2

No

Note that sheets A and B may not be rotated or flipped when pasting them.

Sample Input 3

1 1
#
1 2
##
1 1
#

Sample Output 3

No

No matter how you paste or cut, you cannot cut out a sheet that includes all black squares of sheet B, so you cannot satisfy the first condition. Therefore, print No.

Sample Input 4

3 3
###
...
...
3 3
#..
#..
#..
3 3
..#
..#
###

Sample Output 4

Yes

Problem Statement

Takahashi, who governs the Kingdom of AtCoder, has decided to change the alphabetical order of English lowercase letters.

The new alphabetical order is represented by a string X, which is a permutation of a, b, \ldots, z. The i-th character of X (1 \leq i \leq 26) would be the i-th smallest English lowercase letter in the new order.

The kingdom has N citizens, whose names are S_1, S_2, \dots, S_N, where each S_i (1 \leq i \leq N) consists of lowercase English letters.
Sort these names lexicographically according to the alphabetical order decided by Takahashi.

Constraints

• X is a permutation of a, b, \ldots, z.
• 2 \leq N \leq 50000
• N is an integer.
• 1 \leq |S_i| \leq 10 \, (1 \leq i \leq N)
• S_i consists of lowercase English letters. (1 \leq i \leq N)
• S_i \neq S_j (1 \leq i \lt j \leq N)

Sample Input 1

bacdefghijklmnopqrstuvwxzy
4
abx
bzz
bzy
caa

Sample Output 1

bzz
bzy
abx
caa

In the new alphabetical order set by Takahashi, b is smaller than a and z is smaller than y. Thus, sorting the citizens' names lexicographically would result in bzz, bzy, abx, caa in ascending order.

Sample Input 2

zyxwvutsrqponmlkjihgfedcba
5
a
ab
abc
ac
b

Sample Output 2

b
a
ac
ab
abc

Problem Statement

There is an SNS used by N users, labeled with numbers from 1 to N.

In this SNS, two users can become friends with each other.
Friendship is bidirectional; if user X is a friend of user Y, user Y is always a friend of user X.

Currently, there are M pairs of friendships on the SNS, with the i-th pair consisting of users A_i and B_i.

Determine the maximum number of times the following operation can be performed:

• Operation: Choose three users X, Y, and Z such that X and Y are friends, Y and Z are friends, but X and Z are not. Make X and Z friends.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq A_i < B_i \leq N
• The pairs (A_i, B_i) are distinct.
• All input values are integers.

Sample Input 1

4 3
1 2
2 3
1 4

Sample Output 1

3

Three new friendships with a friend's friend can occur as follows:

• User 1 becomes friends with user 3, who is a friend of their friend (user 2)
• User 3 becomes friends with user 4, who is a friend of their friend (user 1)
• User 2 becomes friends with user 4, who is a friend of their friend (user 1)

There will not be four or more new friendships.

Sample Input 2

3 0

Sample Output 2

0

If there are no initial friendships, no new friendships can occur.

Sample Input 3

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

Sample Output 3

12

Problem Statement

The manufacturing of a certain product requires N processes numbered 1,2,\dots,N.

For each process i, there are two types of machines S_i and T_i available for purchase to handle it.

• Machine S_i: Can process A_i products per day per unit, and costs P_i yen per unit.
• Machine T_i: Can process B_i products per day per unit, and costs Q_i yen per unit.

You can purchase any number of each machine, possibly zero.

Suppose that process i can handle W_i products per day as a result of introducing machines.
Here, we define the production capacity as the minimum of W, that is, \displaystyle \min^{N}_{i=1} W_i.

Given a total budget of X yen, find the maximum achievable production capacity.

Constraints

• All input values are integers.
• 1 \le N \le 100
• 1 \le A_i,B_i \le 100
• 1 \le P_i,Q_i,X \le 10^7

Sample Input 1

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

Sample Output 1

4

For example, by introducing machines as follows, we can achieve a production capacity of 4, which is the maximum possible.

• For process 1, introduce 2 units of machine S_1.
  • This allows processing 4 products per day and costs a total of 10 yen.
• For process 2, introduce 1 unit of machine S_2.
  • This allows processing 1 product per day and costs a total of 1 yen.
• For process 2, introduce 1 unit of machine T_2.
  • This allows processing 3 products per day and costs a total of 3 yen.
• For process 3, introduce 2 units of machine T_3.
  • This allows processing 4 products per day and costs a total of 8 yen.

Sample Input 2

1 10000000
100 1 100 1

Sample Output 2

1000000000

Sample Input 3

1 1
1 10000000 1 10000000

Sample Output 3

0

There may be cases where a positive production capacity cannot be achieved.

Sample Input 4

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

Sample Output 4

894742

Problem Statement

We have a simple directed graph G with N vertices and M edges. The vertices are labeled as Vertex 1, Vertex 2, \ldots, Vertex N. The i-th edge (1\leq i\leq M) goes from Vertex U_i to Vertex V_i.

Takahashi will start at a vertex and repeatedly travel on G from one vertex to another along a directed edge. How many vertices of G have the following condition: Takahashi can start at that vertex and continue traveling indefinitely by carefully choosing the path?

Constraints

• 1 \leq N \leq 2\times 10^5
• 0 \leq M \leq \min(N(N-1), 2\times 10^5)
• 1 \leq U_i,V_i\leq N
• U_i\neq V_i
• (U_i,V_i)\neq (U_j,V_j) if i\neq j.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

4

When starting at Vertex 2, Takahashi can continue traveling indefinitely: 2 \to 3 \to 4 \to 2 \to 3 \to \cdots The same goes when starting at Vertex 3 or Vertex 4. From Vertex 1, he can first go to Vertex 2 and then continue traveling indefinitely again.
On the other hand, from Vertex 5, he cannot move at all.

Thus, four vertices ―Vertex 1, 2, 3, and 4― satisfy the conditions, so 4 should be printed.

Sample Input 2

3 2
1 2
2 1

Sample Output 2

2

Note that, in a simple directed graph, there may be two edges in opposite directions between the same pair of vertices. Additionally, G may not be connected.