Problem Statement

You are given integers A, B, and C.
Determine whether A^2 + B^2 < C^2 holds.

Constraints

• 0 \le A \le 1000
• 0 \le B \le 1000
• 0 \le C \le 1000
• A, B, and C are integers.

Sample Input 1

2 2 4

Sample Output 1

Yes

Since A^2 + B^2 = 2^2 + 2^2 = 8 and C^2 = 4^2 = 16, we have A^2 + B^2 < C^2, so we should print Yes.

Sample Input 2

10 10 10

Sample Output 2

No

Since A^2 + B^2 = 200 and C^2 = 100, A^2 + B^2 < C^2 does not hold.

Sample Input 3

3 4 5

Sample Output 3

No

Problem Statement

You are given sequences of length N each: A = (A_1, A_2, A_3, \dots, A_N) and B = (B_1, B_2, B_3, \dots, B_N).
Find the number of integers x satisfying the following condition:

• A_i \le x \le B_i holds for every integer i such that 1 \le i \le N.

Constraints

• 1 \le N \le 100
• 1 \le A_i \le B_i \le 1000
• All values in input are integers.

Sample Input 1

2
3 2
7 5

Sample Output 1

3

x must satisfy both 3 \le x \le 7 and 2 \le x \le 5.
There are three such integers: 3, 4, and 5.

Sample Input 2

3
1 5 3
10 7 3

Sample Output 2

0

There may be no integer x satisfying the condition.

Sample Input 3

3
3 2 5
6 9 8

Sample Output 3

2

Problem Statement

We have a string S of length 2N.
You are given Q queries on this string.
In the i-th query, given three integers T_i, A_i, and B_i, do the following:

• if T_i = 1: swap the A_i-th and B_i-th characters of S;
• if T_i = 2: swap the first N characters and last N characters of S (the values A_i and B_i are not used).
  For example, if S is FLIP, this query makes it IPFL.

Print the string S after processing all Q queries in the order they are given.

Constraints

• 1 \le N \le 2 \times 10^5
• S is a string of length 2N consisting of uppercase English letters.
• 1 \le Q \le 3 \times 10^5
• T_i is 1 or 2.
• If T_i = 1, 1 \le A_i \lt B_i \le 2N.
• If T_i = 2, A_i = B_i = 0.

Sample Input 1

2
FLIP
2
2 0 0
1 1 4

Sample Output 1

LPFI

The 1-st query swaps the first N characters and last N characters of S, making it IPFL.
The 2-nd query swaps the 1-st and 4-th characters of S, making it LPFI.

Sample Input 2

2
FLIP
6
1 1 3
2 0 0
1 1 2
1 2 3
2 0 0
1 1 4

Sample Output 2

ILPF

Problem Statement

We have a simple undirected graph with N vertices and M edges. The vertices are numbered 1 through N, and the edges are numbered 1 through M.
Edge i connects Vertex A_i and Vertex B_i.
Find the number of ways to paint each vertex in this graph red, green, or blue so that the following condition is satisfied:

• two vertices directly connected by an edge are always painted in different colors.

Here, it is not mandatory to use all the colors.

Constraints

• 1 \le N \le 20
• 0 \le M \le \frac{N(N - 1)}{2}
• 1 \le A_i \le N
• 1 \le B_i \le N
• The given graph is simple (that is, has no multi-edges and no self-loops).

Sample Input 1

3 3
1 2
2 3
3 1

Sample Output 1

6

Let c_1, c_2, c_3 be the colors of Vertices 1, 2, 3 and R, G, B denote red, green, blue, respectively. There are six ways to satisfy the condition:

• c_1c_2c_3 = RGB
• c_1c_2c_3 = RBG
• c_1c_2c_3 = GRB
• c_1c_2c_3 = GBR
• c_1c_2c_3 = BRG
• c_1c_2c_3 = BGR

Sample Input 2

3 0

Sample Output 2

27

Since the graph has no edge, we can freely choose the colors of the vertices.

Sample Input 3

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

Sample Output 3

0

There may be no way to satisfy the condition.

Sample Input 4

20 0

Sample Output 4

3486784401

The answer may not fit into the 32-bit signed integer type.

Problem Statement

Print the number of sequences a that are permutations of (1, 2, 3, \dots, N) and satisfy the following condition:

• for every integer i such that 1 \le i \le M, at most Z_i numbers among a_1, a_2, a_3, \dots, a_{X_i} are less than or equal to Y_i .

Constraints

• 2 \le N \le 18
• 0 \le M \le 100
• 1 \le X_i \lt N
• 1 \le Y_i \lt N
• 0 \le Z_i \lt N
• All values in input are integers.

Sample Input 1

3 1
2 2 1

Sample Output 1

4

The four sequences a satisfying the condition are:

• (1, 3, 2)
• (2, 3, 1)
• (3, 1, 2)
• (3, 2, 1)

(1, 2, 3) and (2, 1, 3) violate the condition, since each of them has two numbers less than or equal to 2 among a_1, a_2.

Sample Input 2

5 2
3 3 2
4 4 3

Sample Output 2

90

Sample Input 3

18 0

Sample Output 3

6402373705728000

Problem Statement

We have a simple undirected graph with N vertices and M edges. The vertices are numbered 1 through N and the edges are numbered 1 through M.
Edge i connects Vertex X_i and Vertex Y_i. Initially, Vertex i has an integer A_i written on it.
You will do the following operation K times:

• Choose one from the M edges uniformly at random and independently from other choices. Let x be the arithmetic mean of the numbers written on the two vertices connected by that edge. Replace each number written on those vertices with x.

For each vertex i, find the expected value of the number written on that vertex after K operations, and print it modulo (10^9 + 7) as described in Notes.

Notes

When printing a rational number, first, represent it as a fraction \frac{y}{x}, where x and y are integers and x is not divisible by (10^9+7) (under the Constraints of this problem, such a representation is always possible).
Then, print the only integer z between 0 and (10^9+6) (inclusive) such that xz \equiv y \pmod {10^9+7}.

Constraints

• 2 \le N \le 100
• 1 \le M \le \frac{N(N - 1)}{2}
• 0 \le K \le 10^9
• 0 \le A_i \le 10^9
• 1 \le X_i \le N
• 1 \le Y_i \le N
• The given graph is simple.
• All values in input are integers.

Sample Input 1

3 2 1
3 1 5
1 2
1 3

Sample Output 1

3
500000005
500000008

• If Edge 1 is chosen in the only operation: the vertices written on Vertices 1, 2, 3 will be 2, 2, 5, respectively.
• If Edge 2 is chosen in the only operation: the vertices written on Vertices 1, 2, 3 will be 4, 1, 4, respectively.

Thus, the expected values of the numbers written on Vertices 1, 2, 3 are 3, \frac{3}{2}, \frac{9}{2}, respectively.
If we express them modulo (10^9 + 7) as described in Notes, they will be 3, 500000005, 500000008, respectively.

Sample Input 2

3 2 2
12 48 36
1 2
1 3

Sample Output 2

750000036
36
250000031

• If Edge 1 is chosen in the 1-st operation: The numbers written on Vertices 1, 2, 3 will be 30, 30, 36, respectively.
  • If Edge 1 is chosen in the 2-nd operation: The numbers written on Vertices 1, 2, 3 will be 30, 30, 36, respectively.
  • If Edge 2 is chosen in the 2-nd operation: The numbers written on Vertices 1, 2, 3 will be 33, 30, 33, respectively.
• If Edge 2 is chosen in the 1-st operation: The numbers written on Vertices 1, 2, 3 will be 24, 48, 24, respectively.
  • If Edge 1 is chosen in the 2-nd operation: The numbers written on Vertices 1, 2, 3 will be 36, 36, 24, respectively.
  • If Edge 2 is chosen in the 2-nd operation: The numbers written on Vertices 1, 2, 3 will be 24, 48, 24, respectively.

Each of these four scenarios happen with probability \frac{1}{4}, so the expected values of the numbers written on Vertices 1, 2, 3 are \frac{123}{4}, \frac{144}{4} (=36), \frac{117}{4}, respectively.

Sample Input 3

4 5 1000
578 173 489 910
1 2
2 3
3 4
4 1
1 3

Sample Output 3

201113830
45921509
67803140
685163678