Problem Statement

Given a positive integer N, print a string of N zeros and N+1 ones where 0 and 1 alternate.

Constraints

• N is an integer.
• 1 \leq N \leq 100

Sample Input 1

4

Sample Output 1

101010101

A string of four zeros and five ones where 0 and 1 alternate is 101010101.

Sample Input 2

1

Sample Output 2

101

Sample Input 3

10

Sample Output 3

101010101010101010101

Problem Statement

You are given a string S of length 6. It is guaranteed that the first three characters of S are ABC and the last three characters are digits.

Determine if S is the abbreviation of a contest held and concluded on AtCoder before the start of this contest.

Here, a string T is "the abbreviation of a contest held and concluded on AtCoder before the start of this contest" if and only if it equals one of the following 348 strings:

ABC001, ABC002, \ldots, ABC314, ABC315, ABC317, ABC318, \ldots, ABC348, ABC349.

Note that ABC316 is not included.

Constraints

• S is a string of length 6 where the first three characters are ABC and the last three characters are digits.

Sample Input 1

ABC349

Sample Output 1

Yes

ABC349 is the abbreviation of a contest held and concluded on AtCoder last week.

Sample Input 2

ABC350

Sample Output 2

No

ABC350 is this contest, which has not concluded yet.

Sample Input 3

ABC316

Sample Output 3

No

ABC316 was not held on AtCoder.

Problem Statement

We have a circular pizza.
Takahashi will cut this pizza using a sequence A of length N, according to the following procedure.

• First, make a cut from the center in the 12 o'clock direction.
• Next, do N operations. The i-th operation is as follows.
  • Rotate the pizza A_i degrees clockwise.
  • Then, make a cut from the center in the 12 o'clock direction.

For example, if A=(90,180,45,195), the procedure cuts the pizza as follows.

Find the center angle of the largest pizza after the procedure.

Constraints

• All values in input are integers.
• 1 \le N \le 359
• 1 \le A_i \le 359
• There will be no multiple cuts at the same position.

Sample Input 1

4
90 180 45 195

Sample Output 1

120

This input coincides with the example in the Problem Statement.
The center angle of the largest pizza is 120 degrees.

Sample Input 2

1
1

Sample Output 2

359

Sample Input 3

10
215 137 320 339 341 41 44 18 241 149

Sample Output 3

170

Problem Statement

N participants, numbered 1 to N, will participate in a contest with M problems, numbered 1 to M.

For an integer i between 1 and N and an integer j between 1 and M, participant i can solve problem j if the j-th character of S_i is o, and cannot solve it if that character is x.

The participants must be in pairs. Print the number of ways to form a pair of participants who can collectively solve all the M problems.

More formally, print the number of pairs (x,y) of integers satisfying 1\leq x < y\leq N such that for any integer j between 1 and M, at least one of participant x and participant y can solve problem j.

Constraints

• N is an integer between 2 and 30, inclusive.
• M is an integer between 1 and 30, inclusive.
• S_i is a string of length M consisting of o and x.

Sample Input 1

5 5
ooooo
oooxx
xxooo
oxoxo
xxxxx

Sample Output 1

5

The following five pairs satisfy the condition: participants 1 and 2, participants 1 and 3, participants 1 and 4, participants 1 and 5, and participants 2 and 3.

On the other hand, the pair of participants 2 and 4, for instance, does not satisfy the condition because they cannot solve problem 4.

Sample Input 2

3 2
ox
xo
xx

Sample Output 2

1

Sample Input 3

2 4
xxxx
oxox

Sample Output 3

0

Problem Statement

You are given a sequence A=(A_1,A_2,\ldots,A_N) of length N consisting of non-negative integers.

Determine if there is an even number represented as the sum of two different elements of A. If it exists, find the maximum such number.

Constraints

• 2\leq N \leq 2\times 10^5
• 0\leq A_i\leq 10^9
• The elements of A are distinct.
• All values in the input are integers.

Sample Input 1

3
2 3 4

Sample Output 1

6

The values represented as the sum of two distinct elements of A are 5, 6, and 7. We have an even number here, and the maximum is 6.

Sample Input 2

2
1 0

Sample Output 2

-1

The value represented as the sum of two distinct elements of A is 1. We have no even number here, so -1 should be printed.

Problem Statement

You are given simple undirected graphs G and H, each with N vertices: vertices 1, 2, \ldots, N. Graph G has M_G edges, and its i-th edge (1\leq i\leq M_G) connects vertices u_i and v_i. Graph H has M_H edges, and its i-th edge (1\leq i\leq M_H) connects vertices a_i and b_i.

You can perform the following operation on graph H any number of times, possibly zero.

• Choose a pair of integers (i,j) satisfying 1\leq i<j\leq N. Pay A_{i,j} yen, and if there is no edge between vertices i and j in H, add one; if there is, remove it.

Find the minimum total cost required to make G and H isomorphic.

Constraints

• 1\leq N\leq8
• 0\leq M _ G\leq\dfrac{N(N-1)}2
• 0\leq M _ H\leq\dfrac{N(N-1)}2
• 1\leq u _ i\lt v _ i\leq N\ (1\leq i\leq M _ G)
• (u _ i,v _ i)\neq(u _ j,v _ j)\ (1\leq i\lt j\leq M _ G)
• 1\leq a _ i\lt b _ i\leq N\ (1\leq i\leq M _ H)
• (a _ i,b _ i)\neq(a _ j,b _ j)\ (1\leq i\lt j\leq M _ H)
• 1\leq A _ {i,j}\leq 10 ^ 6\ (1\leq i\lt j\leq N)
• All input values are integers.

Sample Input 1

5
4
1 2
2 3
3 4
4 5
4
1 2
1 3
1 4
1 5
3 1 4 1
5 9 2
6 5
3

Sample Output 1

9

The given graphs are as follows:

For example, you can perform the following four operations on H to make it isomorphic to G at a cost of 9 yen.

• Choose (i,j)=(1,3). There is an edge between vertices 1 and 3 in H, so pay 1 yen to remove it.
• Choose (i,j)=(2,5). There is no edge between vertices 2 and 5 in H, so pay 2 yen to add it.
• Choose (i,j)=(1,5). There is an edge between vertices 1 and 5 in H, so pay 1 yen to remove it.
• Choose (i,j)=(3,5). There is no edge between vertices 3 and 5 in H, so pay 5 yen to add it.

After these operations, H becomes:

You cannot make G and H isomorphic at a cost less than 9 yen, so print 9.

Sample Input 2

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

Sample Output 2

3

For example, performing the operations (i,j)=(2,3),(2,4),(3,4) on H will make it isomorphic to G.

Sample Input 3

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

Sample Output 3

5

For example, performing the operation (i,j)=(4,5) once will make G and H isomorphic.

Sample Input 4

2
0
0
371

Sample Output 4

0

Note that G and H may have no edges.

Also, it is possible that no operations are needed.

Sample Input 5

8
13
1 8
5 7
4 6
1 5
7 8
1 6
1 2
5 8
2 6
5 6
6 7
3 7
4 8
15
3 5
1 7
4 6
3 8
7 8
1 2
5 6
1 6
1 5
1 4
2 8
2 6
2 4
4 7
1 3
7483 1694 5868 3296 9723 5299 4326
5195 4088 5871 1384 2491 6562
1149 6326 2996 9845 7557
4041 7720 1554 5060
8329 8541 3530
4652 3874
3748

Sample Output 5

21214

Problem Statement

There is an infinitely large two-dimensional grid, with a campfire at coordinate (0,0).
At time t=0, smoke exists only at cell (0,0).

You are given a length-N string S consisting of N, W, S, E. At times t=1,2,\dots,N, the following happen in order:

• Wind blows, and all the smoke present at that time moves as follows:
  • If the t-th character of S is N, smoke in cell (r,c) moves to cell (r-1,c).
  • If it is W, smoke in cell (r,c) moves to cell (r,c-1).
  • If it is S, smoke in cell (r,c) moves to cell (r+1,c).
  • If it is E, smoke in cell (r,c) moves to cell (r,c+1).
• If there is no smoke in cell (0,0), new smoke is generated at cell (0,0).

Takahashi is standing at cell (R,C).
For each integer 1 \le t \le N, determine if smoke exists at cell (R,C) at time t+0.5, and print the response according to the required format.

Constraints

• N is an integer between 1 and 200000, inclusive.
• S is a length N string consisting of N, W, S, E.
• R and C are integers between -N and N, inclusive.
• (R,C) \neq (0,0)

Sample Input 1

6 -2 1
NNEEWS

Sample Output 1

001010

At times 1.5,2.5,4.5,6.5, there is no smoke at cell (-2,1). At times 3.5,5.5, there is smoke at cell (-2,1).
Hence, output 001010.

In the figures below, taking cell (0,0) with the campfire as a reference, cell (r,c) is drawn:

• -r cells up if r < 0,
• r cells down if r \ge 0,
• -c cells left if c < 0,
• c cells right if c \ge 0.

The grid at time 0.5 looks like:

The grid at time 1.5 looks like:

The grid at time 2.5 looks like:

The grid at time 3.5 looks like:

The grid at time 4.5 looks like:

The grid at time 5.5 looks like:

The grid at time 6.5 looks like:

Sample Input 2

10 1 2
NEESESWEES

Sample Output 2

0001101011

Sample Input 3

20 -1 -2
WWNNWSWEWNSWWENSNWWN

Sample Output 3

00100111111000101111

Problem Statement

You are given a simple undirected graph with N vertices numbered 1 to N and M edges numbered 1 to M. Edge i connects vertex u_i and vertex v_i. The degree of each vertex is at most 10.
Let K be the number of simple paths (paths without repeated vertices) starting from vertex 1. Print \min(K, 10^6).

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq \min \left(2 \times 10^5, \frac{N(N-1)}{2}\right)
• 1 \leq u_i, v_i \leq N
• The given graph is simple.
• The degree of each vertex in the given graph is at most 10.
• All values in the input are integers.

Sample Input 1

4 2
1 2
2 3

Sample Output 1

3

We have the following three paths that count. (Note that a path of length 0 also counts.)

• Vertex 1;
• vertex 1, vertex 2;
• vertex 1, vertex 2, vertex 3.

Sample Input 2

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

Sample Output 2

16

Sample Input 3

8 21
2 6
1 3
5 6
3 8
3 6
4 7
4 6
3 4
1 5
2 4
1 2
2 7
1 4
3 5
2 5
2 3
4 5
3 7
6 7
5 7
2 8

Sample Output 3

2023

Problem Statement

There are N people, numbered 1 to N.

A competition was held among these N people, and they were ranked accordingly. The following information is given about their ranks:

• Each person has a unique rank.
• For each 1 \leq i \leq M, if person A_i is ranked x-th and person B_i is ranked y-th, then x - y = C_i.

The given input guarantees that there is at least one possible ranking that does not contradict the given information.

Answer N queries. The answer to the i-th query is an integer determined as follows:

• If the rank of person i can be uniquely determined, return that rank. Otherwise, return -1.

Constraints

• 2 \leq N \leq 16
• 0 \leq M \leq \frac{N(N - 1)}{2}
• 1 \leq A_i, B_i \leq N
• 1 \leq C_i \leq N - 1
• (A_i, B_i) \neq (A_j, B_j) (i \neq j)
• There is at least one possible ranking that does not contradict the given information.
• All input values are integers.

Sample Input 1

5 2
2 3 3
5 4 3

Sample Output 1

3 -1 -1 -1 -1

Let X_i be the rank of person i. Then, (X_1, X_2, X_3, X_4, X_5) could be (3, 4, 1, 2, 5) or (3, 5, 2, 1, 4).

Therefore, the answer to the 1-st query is 3, and the answers to the 2-nd, 3-rd, 4-th, and 5-th queries are -1.

Sample Input 2

3 0

Sample Output 2

-1 -1 -1

Sample Input 3

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

Sample Output 3

1 -1 -1 -1 -1 -1 -1 8