raw_problem:
The following diagram shows a billiard table of a special quadrilateral shape.
The four angles $A, B, C, D$ are $120^\circ, 90^\circ, 60^\circ, 90^\circ$ respectively, and the lengths $AB$ and $AD$ are equal.

The diagram on the left shows the trace of an infinitesimally small billiard ball, departing from point $A$, bouncing twice on the edges of the table, and finally returning back to point $A$. The diagram on the right shows another such trace, but this time bouncing eight times:

The table has no friction and all bounces are perfect elastic collisions.

Note that no bounce should happen on any of the corners, as the behaviour would be unpredictable.

Let $B(N)$ be the number of possible traces of the ball, departing from point $A$, bouncing at most $N$ times on the edges and returning back to point $A$.

For example, $B(10) = 6$, $B(100) = 478$, $B(1000) = 45790$.

Find $B(10^9)$.

problem:
The following diagram shows a billiard table of a special quadrilateral shape.
The four angles $A, B, C, D$ are $120^\circ, 90^\circ, 60^\circ, 90^\circ$ respectively, and the lengths $AB$ and $AD$ are equal.

![image](images/ep_786/1.png)

The diagram on the left shows the trace of an infinitesimally small billiard ball, departing from point $A$, bouncing twice on the edges of the table, and finally returning back to point $A$. The diagram on the right shows another such trace, but this time bouncing eight times:

![image](images/ep_786/2.png)

The table has no friction and all bounces are perfect elastic collisions.
Note that no bounce should happen on any of the corners, as the behaviour would be unpredictable.

Let $B(N)$ be the number of possible traces of the ball, departing from point $A$, bouncing at most $N$ times on the edges and returning back to point $A$.

For example, $B(10) = 6$, $B(100) = 478$, $B(1000) = 45790$.

Find $B(10^9)$.

question:
The following diagram shows a billiard table of a special quadrilateral shape.
The four angles $A, B, C, D$ are $120^\circ, 90^\circ, 60^\circ, 90^\circ$ respectively, and the lengths $AB$ and $AD$ are equal.

![image](1.png)

The diagram on the left shows the trace of an infinitesimally small billiard ball, departing from point $A$, bouncing twice on the edges of the table, and finally returning back to point $A$. The diagram on the right shows another such trace, but this time bouncing eight times:

![image](2.png)

The table has no friction and all bounces are perfect elastic collisions.
Note that no bounce should happen on any of the corners, as the behaviour would be unpredictable.

Let $B(N)$ be the number of possible traces of the ball, departing from point $A$, bouncing at most $N$ times on the edges and returning back to point $A$.

For example, $B(10) = 6$, $B(100) = 478$, $B(1000) = 45790$.

Find $B(10^9)$.

image_tags:
2D Geometry
2D Geometry

data_split: test

source: project euler


E. Verifying Kingdom

problem_index: E

time_limit: 2 seconds

memory_limit: 256 megabytes

note:
For the first sample, the judge has the hidden tree:
![image](images/cf_772_E/1.png)
Here is a more readable format of the interaction:
![image](images/cf_772_E/2.png)
8 6 9 8 9 7 -1 6 7

source: codeforces

raw_problem:
E. Verifying Kingdom

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

This is an interactive problem.

The judge has a hidden rooted full binary tree with n leaves. A full binary tree is one where every node has either 0 or 2 children. The nodes with 0 children are called the leaves of the tree. Since this is a full binary tree, there are exactly 2n - 1 nodes in the tree. The leaves of the judge's tree has labels from 1 to n. You would like to reconstruct a tree that is isomorphic to the judge's tree. To do this, you can ask some questions.

A question consists of printing the label of three distinct leaves a1, a2, a3. Let the depth of a node be the shortest distance from the node to the root of the tree. Let LCA(a, b) denote the node with maximum depth that is a common ancestor of the nodes a and b.

Consider X = LCA(a1, a2), Y = LCA(a2, a3), Z = LCA(a3, a1). The judge will tell you which one of X, Y, Z has the maximum depth. Note, this pair is uniquely determined since the tree is a binary tree; there can't be any ties.

More specifically, if X (or Y, Z respectively) maximizes the depth, the judge will respond with the string "X" (or "Y", "Z" respectively).

You may only ask at most 10·n questions.

Input

The first line of input will contain a single integer n (3 ≤ n ≤ 1 000) — the number of leaves in the tree.

Output

To print the final answer, print out the string "-1" on its own line. Then, the next line should contain 2n - 1 integers. The i-th integer should be the parent of the i-th node, or -1, if it is the root.

Your answer will be judged correct if your output is isomorphic to the judge's tree. In particular, the labels of the leaves do not need to be labeled from 1 to n. Here, isomorphic means that there exists a permutation π such that node i is the parent of node j in the judge tree if and only node π(i) is the parent of node π(j) in your tree.

Interaction

To ask a question, print out three distinct integers a1, a2, a3. These integers should be between 1 and n, inclusive.

The judge will respond with a single character, either "X", "Y", "Z".

If the string is "X" (or "Y", "Z" respectively), that means the pair (a1, a2) (or (a2, a3), (a3, a1) respectively) has the deepest LCA among the three pairs.

You may only ask a question at most 10·n times, otherwise, you will get Wrong Answer.

When you are ready to answer, print out a single integer "-1" on its own line. The next line should contain 2n - 1 integers. The i-th integer should be the parent of the i-th node, or -1, if it is the root. Do not forget to flush the final answer as well. Printing the answer does not count as asking a question.

You will get Wrong Answer verdict if

 Your question or answers are not in the format described in this statement.

 You ask strictly more than 10·n questions.

 Your question contains duplicate indices.

 Your final answer is not isomorphic to the judge tree.

You will get Idleness Limit Exceeded if you don't print anything or if you forget to flush the output, including for the final answer (more info about flushing output below).

To flush you can use (just after printing an integer and end-of-line):

 fflush(stdout) in C++;

 System.out.flush() in Java;

 stdout.flush() in Python;

 flush(output) in Pascal;

 See the documentation for other languages.

If at any moment your program reads -1 as an answer, it should immediately exit normally (for example, by calling exit(0)). You will get Wrong Answer in this case, it means that you made more queries than allowed, or made an invalid query. If you ignore this, you can get other verdicts since your program will continue to read from a closed stream.

Hacking To hack someone, use the following format

n
p_1 p_2 ... p_{2n-1}

This denotes a tree where the parent of the i-th node is pi (pi =  - 1 or n < pi ≤ 2n - 1). If pi is equal to -1, then node i is the root. This input must describe a valid full rooted binary tree.

Of course, contestant programs will not be able to see this input.

Example

Input

5
X
Z
Y
Y
X

Output

1 4 2
1 2 4
2 4 1
2 3 5
2 4 3
-1
-1 1 1 2 2 3 3 6 6

Note

For the first sample, the judge has the hidden tree:

Here is a more readable format of the interaction:
 The last line can also be 8 6 9 8 9 7 -1 6 7.

question:
This is an interactive problem.
The judge has a hidden rooted full binary tree with n leaves. A full binary tree is one where every node has either 0 or 2 children. The nodes with 0 children are called the leaves of the tree. Since this is a full binary tree, there are exactly 2n - 1 nodes in the tree. The leaves of the judge's tree has labels from 1 to n. You would like to reconstruct a tree that is isomorphic to the judge's tree. To do this, you can ask some questions.
A question consists of printing the label of three distinct leaves a_{1}, a_{2}, a_{3}. Let the depth of a node be the shortest distance from the node to the root of the tree. Let LCA(a, b) denote the node with maximum depth that is a common ancestor of the nodes a and b.
Consider X = LCA(a_{1}, a_{2}), Y = LCA(a_{2}, a_{3}), Z = LCA(a_{3}, a_{1}). The judge will tell you which one of X, Y, Z has the maximum depth. Note, this pair is uniquely determined since the tree is a binary tree; there can't be any ties.
More specifically, if X (or Y, Z respectively) maximizes the depth, the judge will respond with the string "X" (or "Y", "Z" respectively).
You may only ask at most 10·n questions.

Input
The first line of input will contain a single integer n (3 ≤ n ≤ 1 000) — the number of leaves in the tree.

Output
To print the final answer, print out the string "-1" on its own line. Then, the next line should contain 2n - 1 integers. The i-th integer should be the parent of the i-th node, or -1, if it is the root.
Your answer will be judged correct if your output is isomorphic to the judge's tree. In particular, the labels of the leaves do not need to be labeled from 1 to n. Here, isomorphic means that there exists a permutation π such that node i is the parent of node j in the judge tree if and only node π(i) is the parent of node π(j) in your tree.

Interaction
To ask a question, print out three distinct integers a_{1}, a_{2}, a_{3}. These integers should be between 1 and n, inclusive.
The judge will respond with a single character, either "X", "Y", "Z".
If the string is "X" (or "Y", "Z" respectively), that means the pair (a_{1}, a_{2}) (or (a_{2}, a_{3}), (a_{3}, a_{1}) respectively) has the deepest LCA among the three pairs.
You may only ask a question at most 10·n times, otherwise, you will get Wrong Answer.
When you are ready to answer, print out a single integer "-1" on its own line. The next line should contain 2n - 1 integers. The i-th integer should be the parent of the i-th node, or -1, if it is the root. Do not forget to flush the final answer as well. Printing the answer does not count as asking a question.
You will get Wrong Answer verdict if
 -  Your question or answers are not in the format described in this statement. -  You ask strictly more than 10·n questions. -  Your question contains duplicate indices. -  Your final answer is not isomorphic to the judge tree. You will get Idleness Limit Exceeded if you don't print anything or if you forget to flush the output, including for the final answer (more info about flushing output below).
To flush you can use (just after printing an integer and end-of-line):
 -  fflush(stdout) in C++; -  System.out.flush() in Java; -  stdout.flush() in Python; -  flush(output) in Pascal; -  See the documentation for other languages. If at any moment your program reads -1 as an answer, it should immediately exit normally (for example, by calling exit(0)). You will get Wrong Answer in this case, it means that you made more queries than allowed, or made an invalid query. If you ignore this, you can get other verdicts since your program will continue to read from a closed stream.
Hacking To hack someone, use the following format

n
p_1 p_2 ... p_{2n-1}

This denotes a tree where the parent of the i-th node is p_{i} (p_{i} =  - 1 or n < p_{i} ≤ 2n - 1). If p_{i} is equal to -1, then node i is the root. This input must describe a valid full rooted binary tree.
Of course, contestant programs will not be able to see this input.

Example
Input
5
X
Z
Y
Y
X

Output
1 4 2
1 2 4
2 4 1
2 3 5
2 4 3
-1
-1 1 1 2 2 3 3 6 6

Note
For the first sample, the judge has the hidden tree:
![image](1.png)
Here is a more readable format of the interaction:
![image](2.png) The last line can also be 8 6 9 8 9 7 -1 6 7.

tags: ['Tree algorithms', 'Sorting', 'Divide and conquer']

skill_types: ['Sorting']

raw_tags: ['trees', 'binary search', 'interactive', 'divide and conquer']

image_tags: Tree Table

data_split: test


D. Meta-set

problem_index: D

time_limit: 4 seconds

memory_limit: 256 megabytes

note:
Let's draw the cards indicating the first four features. The first feature will indicate the number of objects on a card: $$$1$$$, $$$2$$$, $$$3$$$. The second one is the color: red, green, purple. The third is the shape: oval, diamond, squiggle. The fourth is filling: open, striped, solid.
You can see the first three tests below. For the first two tests, the meta-sets are highlighted.
In the first test, the only meta-set is the five cards $$$(0000,\ 0001,\ 0002,\ 0010,\ 0020)$$$. The sets in it are the triples $$$(0000,\ 0001,\ 0002)$$$ and $$$(0000,\ 0010,\ 0020)$$$. Also, a set is the triple $$$(0100,\ 1000,\ 2200)$$$ which does not belong to any meta-set.
![image](images/cf_1735_D/1.png)
In the second test, the following groups of five cards are meta-sets: $$$(0000,\ 0001,\ 0002,\ 0010,\ 0020)$$$, $$$(0000,\ 0001,\ 0002,\ 0100,\ 0200)$$$, $$$(0000,\ 0010,\ 0020,\ 0100,\ 0200)$$$.
![image](images/cf_1735_D/2.png)
In there third test, there are $$$54$$$ meta-sets.
![image](images/cf_1735_D/3.png)

solutions: ["(n, k) = map(int, input().split())\ncards = [tuple(map(int, input().split())) for _ in range(n)]\n(cards_lookup, counter) = ({card: i for (i, card) in enumerate(cards)}, [0] * (n + 1))\nfor i in range(len(cards) - 1):\n\tfor j in range(i + 1, len(cards)):\n\t\tcounter[cards_lookup.get(tuple((x if x == y else (x + 1 ^ y + 1) - 1 for (x, y) in zip(cards[i], cards[j]))), -1)] += 1\nprint(sum((x * (x - 1) // 2 for x in counter[:-1])))\n", "from collections import defaultdict\nimport sys\ninput = lambda : sys.stdin.readline().rstrip()\nin_il = lambda : list(map(int, input().split()))\nin_sl = lambda : input().split()\nin_i = lambda : int(input())\nMAX_INT = float('inf')\n\ndef solve():\n\t(n, k) = in_il()\n\tcards = []\n\tcards_set = set()\n\tcard_part_of_sets = defaultdict(set)\n\tfor _ in range(n):\n\t\tcard = in_il()\n\t\tcards.append(card)\n\t\tcards_set.add(tuple(card))\n\n\tdef get_third(a, b):\n\t\tthird = [None] * k\n\t\tfor i in range(k):\n\t\t\tif a[i] == b[i]:\n\t\t\t\tthird[i] = a[i]\n\t\t\telse:\n\t\t\t\tthird[i] = 3 - a[i] - b[i]\n\t\tthird = tuple(third)\n\t\treturn third if third in cards_set else None\n\tfor i in range(n):\n\t\tfor j in range(i + 1, n):\n\t\t\tthird = get_third(cards[i], cards[j])\n\t\t\tif third != None:\n\t\t\t\tcardset = [tuple(cards[i]), tuple(cards[j]), third]\n\t\t\t\tcardset.sort()\n\t\t\t\tcardset = tuple(cardset)\n\t\t\t\tcard_part_of_sets[tuple(cards[i])].add(cardset)\n\t\t\t\tcard_part_of_sets[tuple(cards[j])].add(cardset)\n\t\t\t\tcard_part_of_sets[third].add(cardset)\n\tmeta = 0\n\tfor v in card_part_of_sets.values():\n\t\tcount = len(v)\n\t\tmeta += count * (count - 1) // 2\n\tprint(meta)\nsolve()\n"]

source: codeforces

raw_problem:
D. Meta-set

time limit per test
4 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

You like the card board game "Set". Each card contains $$$k$$$ features, each of which is equal to a value from the set $$$\{0, 1, 2\}$$$. The deck contains all possible variants of cards, that is, there are $$$3^k$$$ different cards in total.

A feature for three cards is called good if it is the same for these cards or pairwise distinct. Three cards are called a set if all $$$k$$$ features are good for them.

For example, the cards $$$(0, 0, 0)$$$, $$$(0, 2, 1)$$$, and $$$(0, 1, 2)$$$ form a set, but the cards $$$(0, 2, 2)$$$, $$$(2, 1, 2)$$$, and $$$(1, 2, 0)$$$ do not, as, for example, the last feature is not good.

A group of five cards is called a meta-set, if there is strictly more than one set among them. How many meta-sets there are among given $$$n$$$ distinct cards?

Input

The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^3$$$, $$$1 \le k \le 20$$$) — the number of cards on a table and the number of card features. The description of the cards follows in the next $$$n$$$ lines.

Each line describing a card contains $$$k$$$ integers $$$c_{i, 1}, c_{i, 2}, \ldots, c_{i, k}$$$ ($$$0 \le c_{i, j} \le 2$$$) — card features. It is guaranteed that all cards are distinct.

Output

Output one integer — the number of meta-sets.

Examples

Input

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

Output

1

Input

7 4
0 0 0 0
0 0 0 1
0 0 0 2
0 0 1 0
0 0 2 0
0 1 0 0
0 2 0 0

Output

3

Input

9 2
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2

Output

54

Input

20 4
0 2 0 0
0 2 2 2
0 2 2 1
0 2 0 1
1 2 2 0
1 2 1 0
1 2 2 1
1 2 0 1
1 1 2 2
1 1 0 2
1 1 2 1
1 1 1 1
2 1 2 0
2 1 1 2
2 1 2 1
2 1 1 1
0 1 1 2
0 0 1 0
2 2 0 0
2 0 0 2

Output

0

Note

Let's draw the cards indicating the first four features. The first feature will indicate the number of objects on a card: $$$1$$$, $$$2$$$, $$$3$$$. The second one is the color: red, green, purple. The third is the shape: oval, diamond, squiggle. The fourth is filling: open, striped, solid.

You can see the first three tests below. For the first two tests, the meta-sets are highlighted.

In the first test, the only meta-set is the five cards $$$(0000,\ 0001,\ 0002,\ 0010,\ 0020)$$$. The sets in it are the triples $$$(0000,\ 0001,\ 0002)$$$ and $$$(0000,\ 0010,\ 0020)$$$. Also, a set is the triple $$$(0100,\ 1000,\ 2200)$$$ which does not belong to any meta-set.

In the second test, the following groups of five cards are meta-sets: $$$(0000,\ 0001,\ 0002,\ 0010,\ 0020)$$$, $$$(0000,\ 0001,\ 0002,\ 0100,\ 0200)$$$, $$$(0000,\ 0010,\ 0020,\ 0100,\ 0200)$$$.

In there third test, there are $$$54$$$ meta-sets.

question:
You like the card board game "Set". Each card contains $$$k$$$ features, each of which is equal to a value from the set $$$\{0, 1, 2\}$$$. The deck contains all possible variants of cards, that is, there are $$$3^k$$$ different cards in total.
A feature for three cards is called good if it is the same for these cards or pairwise distinct. Three cards are called a set if all $$$k$$$ features are good for them.
For example, the cards $$$(0, 0, 0)$$$, $$$(0, 2, 1)$$$, and $$$(0, 1, 2)$$$ form a set, but the cards $$$(0, 2, 2)$$$, $$$(2, 1, 2)$$$, and $$$(1, 2, 0)$$$ do not, as, for example, the last feature is not good.
A group of five cards is called a meta-set, if there is strictly more than one set among them. How many meta-sets there are among given $$$n$$$ distinct cards?

Input
The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^3$$$, $$$1 \le k \le 20$$$) — the number of cards on a table and the number of card features. The description of the cards follows in the next $$$n$$$ lines.
Each line describing a card contains $$$k$$$ integers $$$c_{i, 1}, c_{i, 2}, \ldots, c_{i, k}$$$ ($$$0 \le c_{i, j} \le 2$$$) — card features. It is guaranteed that all cards are distinct.

Output
Output one integer — the number of meta-sets.

Examples
Input
8 4
0 0 0 0
0 0 0 1
0 0 0 2
0 0 1 0
0 0 2 0
0 1 0 0
1 0 0 0
2 2 0 0

Output
1

Input
7 4
0 0 0 0
0 0 0 1
0 0 0 2
0 0 1 0
0 0 2 0
0 1 0 0
0 2 0 0

Output
3

Input
9 2
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2

Output
54

Input
20 4
0 2 0 0
0 2 2 2
0 2 2 1
0 2 0 1
1 2 2 0
1 2 1 0
1 2 2 1
1 2 0 1
1 1 2 2
1 1 0 2
1 1 2 1
1 1 1 1
2 1 2 0
2 1 1 2
2 1 2 1
2 1 1 1
0 1 1 2
0 0 1 0
2 2 0 0
2 0 0 2

Output
0

Note
Let's draw the cards indicating the first four features. The first feature will indicate the number of objects on a card: $$$1$$$, $$$2$$$, $$$3$$$. The second one is the color: red, green, purple. The third is the shape: oval, diamond, squiggle. The fourth is filling: open, striped, solid.
You can see the first three tests below. For the first two tests, the meta-sets are highlighted.
In the first test, the only meta-set is the five cards $$$(0000,\ 0001,\ 0002,\ 0010,\ 0020)$$$. The sets in it are the triples $$$(0000,\ 0001,\ 0002)$$$ and $$$(0000,\ 0010,\ 0020)$$$. Also, a set is the triple $$$(0100,\ 1000,\ 2200)$$$ which does not belong to any meta-set.
 ![image](1.png) In the second test, the following groups of five cards are meta-sets: $$$(0000,\ 0001,\ 0002,\ 0010,\ 0020)$$$, $$$(0000,\ 0001,\ 0002,\ 0100,\ 0200)$$$, $$$(0000,\ 0010,\ 0020,\ 0100,\ 0200)$$$.
 ![image](2.png) In there third test, there are $$$54$$$ meta-sets.
 ![image](3.png)

tags: ['String algorithms', 'Combinatorics', 'Complete search', 'Mathematics', 'Data structures']

skill_types: ['Data structures', 'Complete search']

raw_tags: ['data structures', 'combinatorics', 'math', 'hashing', 'brute force']

image_tags: Others Others Others

data_split: test


solutions: ["hist = {}\n\ndef foo(n, a):\n\tif n in hist.keys():\n\t\treturn hist[n]\n\tfor x in a:\n\t\tif n % x == 0:\n\t\t\tif x % 2 == 0:\n\t\t\t\thist[n] = True\n\t\t\t\treturn True\n\t\t\tnn = n // x\n\t\t\tif not foo(nn, a):\n\t\t\t\thist[n] = True\n\t\t\t\treturn True\n\thist[n] = False\n\treturn False\n(n, s) = (int(x) for x in input().split())\na = [int(x) for x in input().split()]\nif foo(n, a):\n\tprint('First')\nelse:\n\tprint('Second')\n", "wintbl = {}\n\ndef firstwins(nstones):\n\tif nstones in wintbl:\n\t\treturn wintbl[nstones]\n\twin = True\n\tfor n in nums:\n\t\tif nstones % n != 0:\n\t\t\tcontinue\n\t\tif n % 2 == 0:\n\t\t\tbreak\n\t\tif not firstwins(nstones // n):\n\t\t\tbreak\n\telse:\n\t\twin = False\n\twintbl[nstones] = win\n\treturn win\n\ndef readints():\n\treturn [int(fld) for fld in input().strip().split()]\n(nstones, nnum) = readints()\nnums = readints()\nprint('First' if firstwins(nstones) else 'Second')\n", "from functools import lru_cache\n(n, m) = map(int, input().split())\nar = tuple(sorted((x for x in map(int, input().split()) if not n % x)))\n\n@lru_cache(maxsize=None)\ndef getwin(r):\n\tnextlayer = tuple((r // x for x in ar if not r % x))\n\tif not nextlayer:\n\t\treturn False\n\tif any((all((d % x for x in ar)) for d in nextlayer)):\n\t\treturn True\n\treturn not all(map(getwin, nextlayer))\nif all((x & 1 for x in ar)):\n\tprint('First' if getwin(n) else 'Second')\nelse:\n\tprint('First')\n", "def solve(n):\n\tif n in D:\n\t\treturn D[n]\n\tfor k in S:\n\t\tif n % k == 0:\n\t\t\tx = n // k\n\t\t\tif solve(x):\n\t\t\t\tif k % 2 == 0:\n\t\t\t\t\tD[n] = True\n\t\t\t\t\treturn True\n\t\t\telse:\n\t\t\t\tD[n] = True\n\t\t\t\treturn True\n\tD[n] = False\n\treturn False\n(n, m) = [int(i) for i in input().split()]\nS = [int(i) for i in input().split()]\nD = {1: False}\nprint('First' if solve(n) else 'Second')\n", "(x, m) = map(int, input().split())\nss = set(map(int, input().split()))\n\ndef mex(ns):\n\ti = 0\n\twhile i in ns:\n\t\ti += 1\n\treturn i\nmemo = {}\n\ndef g(n):\n\tif n in memo:\n\t\treturn memo[n]\n\tgs = set()\n\tfor s in ss:\n\t\tif n % s == 0:\n\t\t\tgs.add(g(n // s) if s % 2 == 1 else 0)\n\tret = mex(gs)\n\tmemo[n] = ret\n\treturn ret\nprint('First' if g(x) else 'Second')\n", "(n, m) = [int(t) for t in input().strip().split(' ')]\ns = sorted([int(t) for t in input().strip().split(' ')])\nq = dict()\nF = 'First'\nS = 'Second'\nLI = 1\nSU = 2\nBO = LI | SU\nq[1] = SU\n\ndef doshit(n):\n\tif n in q:\n\t\treturn q[n]\n\tcurr = 0\n\tfor st in s:\n\t\tif st > n or curr == BO:\n\t\t\tbreak\n\t\tif n % st == 0:\n\t\t\tnewsize = n // st\n\t\t\tif doshit(newsize) == LI:\n\t\t\t\tif st % 2 == 0:\n\t\t\t\t\tcurr |= LI\n\t\t\t\telse:\n\t\t\t\t\tcurr |= SU\n\t\t\telif doshit(newsize) == SU:\n\t\t\t\tcurr |= LI\n\t\t\telif st % 2 == 0:\n\t\t\t\tcurr = BO\n\tif curr == 0:\n\t\tcurr = SU\n\tq[n] = curr\n\treturn curr\nprint(F if doshit(n) != SU else S)\n", "class Solver:\n\n\tdef __init__(self, S):\n\t\tself.cache = {}\n\t\tself.S = S\n\n\tdef __call__(self, x):\n\t\tif x in self.cache:\n\t\t\treturn self.cache[x]\n\t\tresult = 0\n\t\tfor s in S:\n\t\t\tif x % s == 0:\n\t\t\t\tresult = max(1 - s * self(x // s) % 2, result)\n\t\tself.cache[x] = result\n\t\treturn result\n(n, _) = map(int, input().split())\nS = set(map(int, input().split()))\nprint('First' if Solver(S)(n) else 'Second')\n", "import sys\n(n, m) = (int(x) for x in sys.stdin.readline().split())\ns = tuple((int(x) for x in sys.stdin.readline().split()))\nassert len(s) == m\nmemo = {}\n\ndef mex(numbers):\n\ti = 0\n\twhile i in numbers:\n\t\ti += 1\n\treturn i\n\ndef grundy(n, divisors):\n\tif n not in memo:\n\t\tnext_grundies = []\n\t\tfor divisor in divisors:\n\t\t\t(q, r) = divmod(n, divisor)\n\t\t\tif r != 0:\n\t\t\t\tcontinue\n\t\t\tif divisor % 2 == 0:\n\t\t\t\tnext_grundies.append(0)\n\t\t\telse:\n\t\t\t\tnext_grundies.append(grundy(q, divisors))\n\t\tmemo[n] = mex(next_grundies)\n\treturn memo[n]\nif grundy(n, s) == 0:\n\tprint('Second')\nelse:\n\tprint('First')\n", "(n, m) = list(map(int, input().split()))\ns = list(map(int, input().split()))\ns = [x for x in s if n % x == 0]\ns.sort()\nm = len(s)\ndp = {}\n\ndef foo(n):\n\tif n not in dp:\n\t\tdp[n] = foo_act(n)\n\treturn dp[n]\n\ndef foo_act(n):\n\tif n == 0:\n\t\treturn False\n\tfor x in s:\n\t\tif n % x == 0:\n\t\t\tval = foo(n // x)\n\t\t\tif not val:\n\t\t\t\treturn True\n\treturn False\niseven = False\nfor x in s:\n\tif x % 2 == 0:\n\t\tiseven = True\n\t\tbreak\nif iseven:\n\tprint('First')\nelse:\n\tprint(foo(n) * 'First' + (not foo(n)) * 'Second')\n", "(n, _) = input().strip().split()\nn = int(n)\nS = set(map(int, input().strip().split()))\nS = set(filter(lambda x: n % x == 0, S))\ncache = {1: 2}\n\ndef WhoWins(n):\n\tif n not in cache:\n\t\tfor s in S:\n\t\t\tif n % s == 0:\n\t\t\t\tnn = n // s\n\t\t\t\tif WhoWins(nn) == 2:\n\t\t\t\t\tcache[n] = 1\n\t\t\t\t\tbreak\n\t\telse:\n\t\t\tcache[n] = 2\n\treturn cache[n]\nfor s in S:\n\tif n % s == 0 and s % 2 == 0:\n\t\tprint('First')\n\t\tbreak\nelse:\n\tret = WhoWins(n)\n\tprint('First' if ret == 1 else 'Second')\n", "from itertools import count\n(n, m) = [int(x) for x in input().split()]\ns = [int(x) for x in input().split()]\n\ndef mex(s):\n\tfor i in count():\n\t\tif i not in s:\n\t\t\treturn i\nmemo = {}\n\ndef grundy(n):\n\tif n not in memo:\n\t\tneighbors = set()\n\t\tfor i in range(m):\n\t\t\tif n % s[i] == 0:\n\t\t\t\tneighbors.add(grundy(n // s[i]) if s[i] % 2 == 1 else 0)\n\t\tmemo[n] = mex(neighbors)\n\treturn memo[n]\nif grundy(n) != 0:\n\tprint('First')\nelse:\n\tprint('Second')\n", "(n, m) = map(int, input().split())\nmv = list(map(int, input().split()))\nmemo = {1: False}\n\ndef valM(x):\n\tif x not in memo:\n\t\tmemo[x] = val(x)\n\treturn memo[x]\n\ndef val(x):\n\ttemp = [valM(x // v) for v in mv if x % v == 0]\n\treturn not all(temp)\n\ndef testEven(x):\n\treturn any([v & 1 == 0 for v in mv if x % v == 0])\nif testEven(n) or valM(n):\n\tprint('First')\nelse:\n\tprint('Second')\n", "def memoize(f):\n\n\tclass memodict(dict):\n\n\t\tdef __init__(self, f):\n\t\t\tself.f = f\n\n\t\tdef __call__(self, *args):\n\t\t\treturn self[args]\n\n\t\tdef __missing__(self, key):\n\t\t\tret = self[key] = self.f(*key)\n\t\t\treturn ret\n\treturn memodict(f)\n\n@memoize\ndef spragueGrundy(n, s):\n\tfollowerScores = set([])\n\tfor x in s:\n\t\tif n % x != 0:\n\t\t\tcontinue\n\t\tif x % 2 == 0:\n\t\t\tfollowerScores.add(0)\n\t\telse:\n\t\t\tfollowerScores.add(spragueGrundy(n // x, s))\n\treturn mex(followerScores)\n\ndef mex(scores):\n\tsc = list(scores)\n\tsc.sort()\n\tfor i in range(len(sc)):\n\t\tif sc[i] != i:\n\t\t\treturn i\n\treturn len(sc)\n(n, m) = map(int, input().strip().split())\ns = tuple(map(int, input().strip().split()))\nif spragueGrundy(n, s) == 0:\n\tprint('Second')\nelse:\n\tprint('First')\n", "(n, m) = map(int, input().split())\nfactors = {}\nl = []\nfor x in input().split():\n\tif n % int(x) == 0:\n\t\tl.append(int(x))\n\ndef game(num):\n\tans = 1\n\tif num in factors.keys():\n\t\treturn factors[num]\n\telse:\n\t\tfor s in l:\n\t\t\tif num % s == 0:\n\t\t\t\tif num // s % 2 == 0 or game(num // s) == 0:\n\t\t\t\t\tfactors[num] = 1\n\t\t\t\t\treturn 1\n\t\treturn 0\nif game(n):\n\tprint('First')\nelse:\n\tprint('Second')\n", "def rints():\n\treturn list(map(int, input().split()))\n\ndef ri():\n\treturn int(input())\n\ndef solve(n, divs):\n\tfor d in divs:\n\t\tif not d & 1 and n % d == 0:\n\t\t\treturn 1\n\n\tdef rec_solve(n, cache):\n\t\tif n not in cache:\n\t\t\tfor d in divs:\n\t\t\t\tif n % d == 0:\n\t\t\t\t\tif rec_solve(n // d, cache) == 0:\n\t\t\t\t\t\tcache[n] = 1\n\t\t\t\t\t\tbreak\n\t\t\telse:\n\t\t\t\tcache[n] = 0\n\t\treturn cache[n]\n\treturn rec_solve(n, {})\n\ndef main():\n\t(n, m) = rints()\n\tdivs = rints()\n\tprint('First' if solve(n, divs) == 1 else 'Second')\nmain()\n", "from functools import lru_cache\nr = lambda : map(int, input().split())\n(n, m) = r()\na = list(r())\n\n@lru_cache(maxsize=None)\ndef go(n):\n\tfor x in a:\n\t\tif n % x == 0:\n\t\t\tif x & 1 == 0:\n\t\t\t\treturn True\n\t\t\telif not go(n // x):\n\t\t\t\treturn True\n\treturn False\nprint('First' if go(n) else 'Second')\n", "from functools import reduce\nfrom collections import defaultdict\n(n, _) = [int(x) for x in input().split()]\na = [int(x) for x in input().split()]\nl = {n}\nleafs = set()\nlinks = defaultdict(lambda : set())\nlinksV = defaultdict(lambda : 0)\nwin = defaultdict(lambda : 0)\nwhile l:\n\tnl = set()\n\tfor num in l:\n\t\tfound = 0\n\t\tfor den in a:\n\t\t\tif num % den != 0:\n\t\t\t\tcontinue\n\t\t\tval = num // den\n\t\t\tnl.add(val)\n\t\t\tif num not in links[val]:\n\t\t\t\tlinks[val].add(num)\n\t\t\t\tlinksV[num] += 1\n\t\t\tfound = 1\n\t\tif not found:\n\t\t\tleafs.add(num)\n\tl = nl\nnxt = set()\nfor num in leafs:\n\twin[num] = 0\n\tfor parent in links[num]:\n\t\twin[parent] = 1\n\t\tlinksV[parent] -= 1\n\t\tif linksV[parent] == 0:\n\t\t\tnxt.add(parent)\nwhile nxt:\n\tnxt2 = set()\n\tfor num in nxt:\n\t\tfor parent in links[num]:\n\t\t\tocc = parent // num\n\t\t\tval = win[num]\n\t\t\tif occ % 2 == 0:\n\t\t\t\tval ^= win[num]\n\t\t\twin[parent] |= not val\n\t\t\tlinksV[parent] -= 1\n\t\t\tif linksV[parent] == 0:\n\t\t\t\tnxt2.add(parent)\n\tnxt = nxt2\nprint('Second' if win[n] == 0 else 'First')\n", "(n, m) = [int(x) for x in input().split()]\nS = [int(x) for x in input().split()]\nsg = {}\nfor s in S:\n\tsg[s] = 1\n\ndef solve(N, S):\n\tif N in sg:\n\t\treturn sg[N]\n\tmex = []\n\tfor s in S:\n\t\tif N % s == 0:\n\t\t\tif N // s % 2 == 0:\n\t\t\t\tmex.append(0)\n\t\t\telse:\n\t\t\t\tmex.append(solve(N // s, S))\n\tsg_ = 0\n\tfor x in sorted(mex):\n\t\tif x > sg_:\n\t\t\tbreak\n\t\tsg_ += 1\n\tsg[N] = sg_\n\treturn sg_\n\ndef help(N, S):\n\tif solve(N, S) == 0:\n\t\tprint('Second')\n\telse:\n\t\tprint('First')\nhelp(n, S)\n", "d = {}\n\ndef fun(a, n):\n\tif n in d:\n\t\treturn d[n]\n\tflag = False\n\tfor i in a:\n\t\tif n % i == 0:\n\t\t\tflag = True\n\t\t\tbreak\n\tif flag == False:\n\t\td[n] = 0\n\t\treturn 0\n\tfor i in a:\n\t\tif n % i == 0 and i % 2 == 0:\n\t\t\td[n] = 1\n\t\t\treturn 1\n\tfor i in a:\n\t\tif n % i == 0:\n\t\t\tif fun(a, n // i) == 0:\n\t\t\t\td[n] = 1\n\t\t\t\treturn 1\n\td[n] = 0\n\treturn 0\n(n, m) = [int(i) for i in input().split()]\na = [int(i) for i in input().split()]\nif fun(a, n) == 1:\n\tprint('First')\nelse:\n\tprint('Second')\n", "def mex(S):\n\ti = 0\n\twhile i in S:\n\t\ti += 1\n\treturn i\n\ndef sg(pile_size, divisors, cache={}):\n\tkey = pile_size\n\tS = set()\n\tif key in cache:\n\t\treturn cache[key]\n\tif pile_size == 0:\n\t\treturn 0\n\tfor d in divisors:\n\t\tif pile_size % d == 0:\n\t\t\tsize_new_pile = pile_size // d\n\t\t\ts = 0\n\t\t\tif d % 2 == 1:\n\t\t\t\ts = sg(size_new_pile, divisors)\n\t\t\tS.add(s)\n\tcache[key] = mex(S)\n\treturn cache[key]\n(n, m) = map(int, input().split())\ndivisors = list(map(int, input().split()))\nprint(['Second', 'First'][sg(n, divisors) > 0])\n", "(n, m) = [int(x) for x in input().strip().split(' ')]\ns = [int(x) for x in input().strip().split(' ')]\nfor x in s:\n\tif n % x != 0:\n\t\ts.remove(x)\ns = sorted(s)\ns_r = sorted(s, reverse=True)\ncount = 0\nn_b = n\nparts = 1\nfor x in s:\n\twhile n % x == 0:\n\t\ttemp = n // x\n\t\tcount += parts\n\t\tparts = x\n\t\tn = temp\nif count % 2 == 0:\n\tres_1 = 0\nelse:\n\tres_1 = 1\ncount = 0\nn = n_b\nparts = 1\nfor x in s_r:\n\twhile n % x == 0:\n\t\ttemp = n // x\n\t\tcount += parts\n\t\tparts = x\n\t\tn = temp\nif count % 2 == 0:\n\tres_2 = 0\nelse:\n\tres_2 = 1\nif len(s) == 3 and s[2] == 42075 or len(s) == 7:\n\tprint('Second')\nelif len(s) == 3 and s[2] == 4039875:\n\tprint('First')\nelif (res_1 or res_2) == 1:\n\tprint('First')\nelse:\n\tprint('Second')\n", "hist = {}\n\ndef foo(n, a):\n\tif n in hist.keys():\n\t\treturn hist[n]\n\tfor x in a:\n\t\tif n % x == 0:\n\t\t\tif x % 2 == 0:\n\t\t\t\thist[n] = True\n\t\t\t\treturn True\n\t\t\tnn = n // x\n\t\t\tif not foo(nn, a):\n\t\t\t\thist[n] = True\n\t\t\t\treturn True\n\thist[n] = False\n\treturn False\n(n, s) = (int(x) for x in input().split())\na = [int(x) for x in input().split()]\nif foo(n, a):\n\tprint('First')\nelse:\n\tprint('Second')\n", "G = {}\n\ndef grundy(n):\n\tif n not in G:\n\t\tg = set()\n\t\tfor i in D:\n\t\t\tif n % i == 0:\n\t\t\t\tif i & 1:\n\t\t\t\t\tg.add(grundy(n // i))\n\t\t\t\telse:\n\t\t\t\t\tg.add(0)\n\t\ti = 0\n\t\twhile i in g:\n\t\t\ti += 1\n\t\tG[n] = i\n\treturn G[n]\n(N, S) = map(int, input().split())\nD = list(map(int, input().split()))\nprint('First' if grundy(N) else 'Second')\n", "from functools import lru_cache\n\n@lru_cache(None)\ndef grundy(n):\n\tnimbers = set()\n\tfor si in s:\n\t\t(d, r) = divmod(n, si)\n\t\tif r == 0:\n\t\t\tnimbers.add(grundy(d) if si % 2 else 0)\n\tfor i in range(len(nimbers) + 1):\n\t\tif i not in nimbers:\n\t\t\treturn i\n(n, m) = (int(x) for x in input().split())\ns = [int(x) for x in input().split()]\nprint('First' if grundy(n) else 'Second')\n", "import sys\nimport functools\nL = 0\nW = 1\nSC = 2\nFC = 3\nFL = 4\nFW = 5\nsaved_case = {}\n\ndef print_answer(num_stones, divisors):\n\tdivisors = [item for item in divisors if num_stones % item == 0]\n\tfor item in divisors:\n\t\tif item % 2 == 0:\n\t\t\tprint('First')\n\t\t\treturn\n\tsaved_case = {}\n\n\tdef solve_odd_case(num_stones, case_divisors):\n\t\tlower_levels = []\n\t\tcase_divisors = [item for item in case_divisors if num_stones % item == 0]\n\t\tif len(case_divisors) == 0:\n\t\t\treturn 2 ** L\n\t\tfor divisor in case_divisors:\n\t\t\tcase_num = num_stones // divisor\n\t\t\tif case_num in saved_case:\n\t\t\t\tlower_levels.append(saved_case[case_num])\n\t\t\telse:\n\t\t\t\tcase_result = solve_odd_case(case_num, case_divisors)\n\t\t\t\tlower_levels.append(case_result)\n\t\t\t\tsaved_case[case_num] = case_result\n\t\tflag = functools.reduce(lambda x, y: x | y, lower_levels)\n\t\tif flag == 2 ** L:\n\t\t\treturn 2 ** W\n\t\tif flag == 2 ** W:\n\t\t\treturn 2 ** L\n\t\tif flag == 2 ** FC:\n\t\t\treturn 2 ** SC\n\t\tif flag & 2 ** SC:\n\t\t\treturn 2 ** FC\n\t\tif flag & (2 ** L | 2 ** W) == 2 ** L | 2 ** W:\n\t\t\treturn 2 ** FC\n\t\tif flag & (2 ** L | 2 ** FW) == 2 ** L | 2 ** FW:\n\t\t\treturn 2 ** FC\n\t\tif flag & (2 ** W | 2 ** FL) == 2 ** W | 2 ** FL:\n\t\t\treturn 2 ** FC\n\t\tif flag & 2 ** W:\n\t\t\treturn 2 ** FL\n\t\tif flag & 2 ** L:\n\t\t\treturn 2 ** FW\n\t\tif flag & 2 ** FL:\n\t\t\treturn 2 ** FW\n\t\tif flag & 2 ** FW:\n\t\t\treturn 2 ** FL\n\t\traise\n\tresult = solve_odd_case(num_stones, divisors)\n\tif result & (2 ** FC | 2 ** W | 2 ** FW):\n\t\tprint('First')\n\telif result & (2 ** SC | 2 ** L | 2 ** FL):\n\t\tprint('Second')\n\telse:\n\t\traise\nlines = sys.stdin\nnum_stones = int(lines.readline().split(' ')[0])\ndivisors = [int(item) for item in lines.readline().split(' ')]\nprint_answer(num_stones, divisors)\n", "import itertools\nstone_div_cache = {}\n\ndef stone_div_nimber(n):\n\tif n == 1:\n\t\treturn 0\n\tif n in stone_div_cache:\n\t\treturn stone_div_cache[n]\n\treachable = []\n\tfor s in S:\n\t\tif n % s == 0:\n\t\t\treachable.append(stone_div_nimber(n // s) if s % 2 == 1 else 0)\n\treachable = list(sorted(set(reachable)))\n\tres = 0\n\tfor i in itertools.count():\n\t\tif len(reachable) <= i:\n\t\t\tres = i\n\t\t\tbreak\n\t\tif reachable[i] != i:\n\t\t\tres = i\n\t\t\tbreak\n\tstone_div_cache[n] = res\n\treturn res\n(n, m) = [int(x) for x in input().split()]\nS = [int(x) for x in input().split()]\nprint('First' if stone_div_nimber(n) else 'Second')\n", "(n, m) = map(int, input().split())\ns = list(map(int, input().split()))\ngrundy_set = {}\n\ndef grundy(size):\n\tif size in grundy_set:\n\t\treturn grundy_set[size]\n\telse:\n\t\tg = set()\n\t\tfor i in s:\n\t\t\tif size % i == 0:\n\t\t\t\tif i % 2 == 0:\n\t\t\t\t\tg.add(0)\n\t\t\t\telse:\n\t\t\t\t\tg.add(grundy(size // i))\n\t\tm = 0\n\t\twhile m in g:\n\t\t\tm += 1\n\t\tgrundy_set[size] = m\n\t\treturn m\nprint('First' if grundy(n) else 'Second')\n", "def parseInput(f):\n\treturn [f(x) for x in input().split()]\n(n, m) = parseInput(int)\ns = parseInput(int)\nmemo = {}\n\ndef grundy(x):\n\tif x in memo:\n\t\treturn memo[x]\n\tmex = set()\n\tfor d in s:\n\t\tif x >= d and x % d == 0:\n\t\t\tif d % 2:\n\t\t\t\tmex.add(grundy(x // d))\n\t\t\telse:\n\t\t\t\tmex.add(0)\n\tanswer = 0\n\twhile answer in mex:\n\t\tanswer += 1\n\tmemo[x] = answer\n\treturn answer\nanswer = grundy(n)\nprint('First' if answer else 'Second')\n", "(n, m) = map(int, input().split(' '))\nD = [int(x) for x in input().split(' ')]\ncanWin = False\n\ndef win(p):\n\tfor t in D:\n\t\tif p % t == 0 and (not win(p // t)):\n\t\t\treturn True\n\treturn False\nfor x in D:\n\tif n % x == 0 and n // x & 1 == 0:\n\t\tcanWin = True\n\t\tbreak\nif canWin:\n\tprint('First')\nelif n == 450283905890997363:\n\tprint('First')\nelse:\n\tprint('First' if win(n) else 'Second')\n", "import sys\nfrom time import time\n\ndef factor_gen(n, aa):\n\tstack = [(1, 0)]\n\twhile stack:\n\t\t(f, index) = stack.pop()\n\t\tif f > 1 and index == len(aa):\n\t\t\tyield f\n\t\tif index != len(aa):\n\t\t\ta = aa[index]\n\t\t\twhile f <= n and n % f == 0:\n\t\t\t\tstack.append((f, index + 1))\n\t\t\t\tf *= a\n\ndef prime_gen(n):\n\tsieve = [1] * n\n\tfor p in range(2, n):\n\t\tif sieve[p]:\n\t\t\tyield p\n\t\t\tfor i in range(p + p, n, p):\n\t\t\t\tsieve[i] = 0\n\ndef pf_gen(n, prms):\n\tfor p in prms:\n\t\tif p > n:\n\t\t\tbreak\n\t\tcnt = 0\n\t\twhile n % p == 0:\n\t\t\tcnt += 1\n\t\t\tn //= p\n\t\tif cnt:\n\t\t\tyield (p, cnt)\n\tif n > 1:\n\t\tyield (n, 1)\n\ndef build_graph(n, aa):\n\tg = dict()\n\tstack = [n]\n\twhile stack:\n\t\tu = stack.pop()\n\t\tif u not in g:\n\t\t\tg[u] = set()\n\t\t\tfor a in aa:\n\t\t\t\tif u % a == 0:\n\t\t\t\t\tv = u // a\n\t\t\t\t\tg[u].add(v)\n\t\t\t\t\tstack.append(v)\n\treturn g\ntcache = dict()\n\ndef transitions(n, g):\n\tif n in tcache:\n\t\treturn tcache[n]\n\tif n not in g:\n\t\trval = {0}\n\telif not g[n]:\n\t\trval = {0}\n\telse:\n\t\trval = set()\n\t\tfor m in g[n]:\n\t\t\tfor t in transitions(m, g):\n\t\t\t\trval.add(t + 1)\n\ttcache[n] = rval\n\treturn rval\n\ndef mex(ss):\n\tr = 0\n\twhile r in ss:\n\t\tr += 1\n\treturn r\nncache = dict()\n\ndef nimber(n, aa):\n\tif n in ncache:\n\t\treturn ncache[n]\n\tnn = set()\n\tfor a in aa:\n\t\tif n % a == 0:\n\t\t\tk = n // a\n\t\t\tif a % 2 == 1:\n\t\t\t\tnn.add(nimber(k, aa))\n\t\t\telse:\n\t\t\t\tnn.add(0)\n\trval = mex(nn)\n\tncache[n] = rval\n\tprint('\\tn=%d nimber=%d' % (n, rval), file=sys.stderr)\n\treturn rval\n\ndef solve(n, aa, prms):\n\tprint('n=%d aa=%s' % (n, aa), file=sys.stderr)\n\tpfs = tuple(pf_gen(n, prms))\n\tprint('\\tpfs=%s' % (pfs,), file=sys.stderr)\n\tg = build_graph(n, aa)\n\tprint('\\tg=%s' % (sorted(g.items()),), file=sys.stderr)\n\ttt = transitions(n, g)\n\tprint('\\ttt=%s' % (sorted(tt),), file=sys.stderr)\n\treturn nimber(n, aa) > 0\n\trval = 0\n\tprint('cache=%s' % (sorted(cache.items()),), file=sys.stderr)\n\treturn rval\ntm = time()\nN = pow(10, 6)\nprms = tuple(prime_gen(N))\nprint('primes generated: %s %s' % (len(prms), time() - tm), file=sys.stderr)\n(n, _) = map(int, input().split())\naa = list(map(int, input().split()))\nif solve(n, aa, prms):\n\tprint('First')\nelse:\n\tprint('Second')\nprint('time elapsed: %s' % (time() - tm,), file=sys.stderr)\n", "(n, m) = map(int, input().split())\ns = list(map(int, input().split()))\ngrundy_set = {}\n\ndef grundy(size):\n\tif size in grundy_set:\n\t\treturn grundy_set[size]\n\telse:\n\t\tg = set()\n\t\tfor i in s:\n\t\t\tif size % i == 0:\n\t\t\t\tif i % 2 == 0:\n\t\t\t\t\tg.add(0)\n\t\t\t\telse:\n\t\t\t\t\tg.add(grundy(size // i))\n\t\tm = 0\n\t\twhile m in g:\n\t\t\tm += 1\n\t\tgrundy_set[size] = m\n\t\treturn m\nprint('First' if grundy(n) else 'Second')\n", "from functools import lru_cache\n\n@lru_cache(maxsize=None)\ndef grundy(n):\n\tg = 0\n\tG = []\n\tfor s in S:\n\t\tif n % s == 0:\n\t\t\tG.append(0 if s & 1 == 0 else grundy(n // s))\n\t\twhile g in G:\n\t\t\tg += 1\n\treturn g\n\ndef main():\n\tglobal S\n\t(N, M) = map(int, input().split())\n\tS = list(map(int, input().split()))\n\tprint('First' if grundy(N) != 0 else 'Second')\nmain()\n", "hist = {}\n\ndef foo(n, a):\n\tif n in hist.keys():\n\t\treturn hist[n]\n\tfor x in a:\n\t\tif n % x == 0:\n\t\t\tif x % 2 == 0:\n\t\t\t\thist[n] = True\n\t\t\t\treturn True\n\t\t\tnn = n // x\n\t\t\tif not foo(nn, a):\n\t\t\t\thist[n] = True\n\t\t\t\treturn True\n\thist[n] = False\n\treturn False\n(n, s) = (int(x) for x in input().split())\na = [int(x) for x in input().split()]\nif foo(n, a):\n\tprint('First')\nelse:\n\tprint('Second')\n", "(n, m) = (int(i) for i in input().strip().split(' '))\nar = [int(i) for i in input().strip().split(' ') if n % int(i) == 0]\n\ndef t(x, y):\n\treturn x and y\nfrom collections import defaultdict\n\ndef g():\n\treturn -1\nd = defaultdict(g)\nfrom functools import reduce\n\ndef f(n, ar):\n\tif d[n] != -1:\n\t\treturn d[n]\n\tm = len(ar)\n\tfor i in range(m):\n\t\tif n % ar[i] == 0:\n\t\t\tif ar[i] % 2 == 0:\n\t\t\t\td[n] = 1\n\t\t\t\treturn 1\n\t\t\telse:\n\t\t\t\tk = f(n // ar[i], ar)\n\t\t\t\tif k == 0:\n\t\t\t\t\td[n] = 1\n\t\t\t\t\treturn 1\n\td[n] = 0\n\treturn 0\nif f(n, ar):\n\tprint('First')\nelse:\n\tprint('Second')\n", "hist = {}\n\ndef foo(n, a):\n\tif n in hist.keys():\n\t\treturn hist[n]\n\tfor x in a:\n\t\tif n % x == 0:\n\t\t\tif x % 2 == 0:\n\t\t\t\thist[n] = True\n\t\t\t\treturn True\n\t\t\tnn = n // x\n\t\t\tif not foo(nn, a):\n\t\t\t\thist[n] = True\n\t\t\t\treturn True\n\thist[n] = False\n\treturn False\n(n, s) = (int(x) for x in input().split())\na = [int(x) for x in input().split()]\nif foo(n, a):\n\tprint('First')\nelse:\n\tprint('Second')\n", "hist = {}\n\ndef foo(n, a):\n\tif n in hist.keys():\n\t\treturn hist[n]\n\tfor x in a:\n\t\tif n % x == 0:\n\t\t\tif x % 2 == 0:\n\t\t\t\thist[n] = True\n\t\t\t\treturn True\n\t\t\tnn = n // x\n\t\t\tif not foo(nn, a):\n\t\t\t\thist[n] = True\n\t\t\t\treturn True\n\thist[n] = False\n\treturn False\n(n, s) = (int(x) for x in input().split())\na = [int(x) for x in input().split()]\nif foo(n, a):\n\tprint('First')\nelse:\n\tprint('Second')\n", "hist = {}\n\ndef foo(n, a):\n\tif n in hist.keys():\n\t\treturn hist[n]\n\tfor x in a:\n\t\tif n % x == 0:\n\t\t\tif x % 2 == 0:\n\t\t\t\thist[n] = True\n\t\t\t\treturn True\n\t\t\tnn = n // x\n\t\t\tif not foo(nn, a):\n\t\t\t\thist[n] = True\n\t\t\t\treturn True\n\thist[n] = False\n\treturn False\n(n, s) = (int(x) for x in input().split())\na = [int(x) for x in input().split()]\nif foo(n, a):\n\tprint('First')\nelse:\n\tprint('Second')\n", "hist = {}\n\ndef foo(n, a):\n\tif n in hist.keys():\n\t\treturn hist[n]\n\tfor x in a:\n\t\tif n % x == 0:\n\t\t\tif x % 2 == 0:\n\t\t\t\thist[n] = True\n\t\t\t\treturn True\n\t\t\tnn = n // x\n\t\t\tif not foo(nn, a):\n\t\t\t\thist[n] = True\n\t\t\t\treturn True\n\thist[n] = False\n\treturn False\n(n, s) = (int(x) for x in input().split())\na = [int(x) for x in input().split()]\nif foo(n, a):\n\tprint('First')\nelse:\n\tprint('Second')\n", "import math\nimport os\nimport random\nimport re\nimport sys\n\ndef solve(n):\n\tif n in D:\n\t\treturn D[n]\n\tfor k in S:\n\t\tif n % k == 0:\n\t\t\tx = n // k\n\t\t\tif solve(x):\n\t\t\t\tif k % 2 == 0:\n\t\t\t\t\tD[n] = True\n\t\t\t\t\treturn True\n\t\t\telse:\n\t\t\t\tD[n] = True\n\t\t\t\treturn True\n\tD[n] = False\n\treturn False\n(n, m) = [int(i) for i in input().split()]\nS = [int(i) for i in input().split()]\nD = {1: False}\nprint('First' if solve(n) else 'Second')\n", "import math\nimport os\nimport random\nimport re\nimport sys\nhist = {}\n\ndef foo(n, a):\n\tif n in hist.keys():\n\t\treturn hist[n]\n\tfor x in a:\n\t\tif n % x == 0:\n\t\t\tif x % 2 == 0:\n\t\t\t\thist[n] = True\n\t\t\t\treturn True\n\t\t\tnn = n // x\n\t\t\tif not foo(nn, a):\n\t\t\t\thist[n] = True\n\t\t\t\treturn True\n\thist[n] = False\n\treturn False\n(n, s) = (int(x) for x in input().split())\na = [int(x) for x in input().split()]\nif foo(n, a):\n\tprint('First')\nelse:\n\tprint('Second')\n", "hist = {}\n\ndef foo(n, a):\n\tif n in hist.keys():\n\t\treturn hist[n]\n\tfor x in a:\n\t\tif n % x == 0:\n\t\t\tif x % 2 == 0:\n\t\t\t\thist[n] = True\n\t\t\t\treturn True\n\t\t\tnn = n // x\n\t\t\tif not foo(nn, a):\n\t\t\t\thist[n] = True\n\t\t\t\treturn True\n\thist[n] = False\n\treturn False\n(n, s) = (int(x) for x in input().split())\na = [int(x) for x in input().split()]\nif foo(n, a):\n\tprint('First')\nelse:\n\tprint('Second')\n", "hist = {}\n\ndef foo(n, a):\n\tif n in hist.keys():\n\t\treturn hist[n]\n\tfor x in a:\n\t\tif n % x == 0:\n\t\t\tif x % 2 == 0:\n\t\t\t\thist[n] = True\n\t\t\t\treturn True\n\t\t\tnn = n // x\n\t\t\tif not foo(nn, a):\n\t\t\t\thist[n] = True\n\t\t\t\treturn True\n\thist[n] = False\n\treturn False\n(n, s) = (int(x) for x in input().split())\na = [int(x) for x in input().split()]\nif foo(n, a):\n\tprint('First')\nelse:\n\tprint('Second')\n", "hist = {}\n\ndef foo(n, a):\n\tif n in hist.keys():\n\t\treturn hist[n]\n\tfor x in a:\n\t\tif n % x == 0:\n\t\t\tif x % 2 == 0:\n\t\t\t\thist[n] = True\n\t\t\t\treturn True\n\t\t\tnn = n // x\n\t\t\tif not foo(nn, a):\n\t\t\t\thist[n] = True\n\t\t\t\treturn True\n\thist[n] = False\n\treturn False\n(n, s) = (int(x) for x in input().split())\na = [int(x) for x in input().split()]\nif foo(n, a):\n\tprint('First')\nelse:\n\tprint('Second')\n", "hist = {}\n\ndef foo(n, a):\n\tif n in hist.keys():\n\t\treturn hist[n]\n\tfor x in a:\n\t\tif n % x == 0:\n\t\t\tif x % 2 == 0:\n\t\t\t\thist[n] = True\n\t\t\t\treturn True\n\t\t\tnn = n // x\n\t\t\tif not foo(nn, a):\n\t\t\t\thist[n] = True\n\t\t\t\treturn True\n\thist[n] = False\n\treturn False\n(n, s) = (int(x) for x in input().split())\na = [int(x) for x in input().split()]\nif foo(n, a):\n\tprint('First')\nelse:\n\tprint('Second')\n"]

source: hacker rank

question:
Consider the following game:

There are two players, First and Second, sitting in front of a pile of $n$ stones. First always plays first.
There is a set, $\mbox{S}$, of $m$ distinct integers defined as $S=\{s_0,s_1,\ldots,s_{m-1}\}$.
The players move in alternating turns. During each turn, a player chooses some $s_i\in S$ and splits one of the piles into exactly $s_i$ smaller piles of equal size. If no $s_i$ exists that will split one of the available piles into exactly $s_i$ equal smaller piles, the player loses.
Both players always play optimally.

Given $n$, $m$, and the contents of $\mbox{S}$, find and print the winner of the game. If First wins, print First; otherwise, print Second.

Input Format

The first line contains two space-separated integers describing the respective values of $n$ (the size of the initial pile) and $m$ (the size of the set).

The second line contains $m$ distinct space-separated integers describing the respective values of $s_0,s_1,\ldots,s_{m-1}$.

Constraints

$1\leq n\leq10^{18}$
$1\leq m\leq10$
$2\leq s_i\leq10^{18}$

Output Format

Print First if the First player wins the game; otherwise, print Second.

Sample Input 0
15 3
5 2 3

Sample Output 0
Second

Explanation 0

The initial pile has $n=15$ stones, and $S=\{5,2,3\}$. During First's initial turn, they have two options:

Split the initial pile into $5$ equal piles, which forces them to lose after the following sequence of turns:

Split the initial pile into $3$ equal piles, which forces them to lose after the following sequence of turns:

![image](2.png)
Because First never has any possible move that puts them on the path to winning, we print Second as our answer.
![image](2.png)

image_tags: Chessboard Chessboard

data_split: test


C. Knights

problem_index: C

time_limit: 1 second

memory_limit: 256 megabytes

note:
Let's look at second example:
![image](images/cf_1067_C/1.png)
Green zeroes are initial knights. Cell $$$(3, \,\, 3)$$$ is under attack of $$$4$$$ knights in cells $$$(1, \,\, 2)$$$, $$$(2, \,\, 1)$$$, $$$(4, \,\, 1)$$$ and $$$(5, \,\, 2)$$$, therefore Ivan will place a knight in this cell. Cell $$$(4, \,\, 5)$$$ is initially attacked by only $$$3$$$ knights in cells $$$(2, \,\, 6)$$$, $$$(5, \,\, 7)$$$ and $$$(6, \,\, 6)$$$. But new knight in cell $$$(3, \,\, 3)$$$ also attacks cell $$$(4, \,\, 5)$$$, now it is attacked by $$$4$$$ knights and Ivan will place another knight in this cell. There are no more free cells which are attacked by $$$4$$$ or more knights, so the process stops. There are $$$9$$$ knights in the end, which is not less than $$$\lfloor \frac{7^{2}}{10} \rfloor = 4$$$.

solutions: ["import collections, atexit, math, sys, bisect\nsys.setrecursionlimit(1000000)\n\ndef getIntList():\n\treturn list(map(int, input().split()))\ntry:\n\timport numpy\n\n\tdef dprint(*args, **kwargs):\n\t\tprint(*args, **kwargs, file=sys.stderr)\n\tdprint('debug mode')\nexcept Exception:\n\n\tdef dprint(*args, **kwargs):\n\t\tpass\ninId = 0\noutId = 0\nif inId > 0:\n\tdprint('use input', inId)\n\tsys.stdin = open('input' + str(inId) + '.txt', 'r')\nif outId > 0:\n\tdprint('use output', outId)\n\tsys.stdout = open('stdout' + str(outId) + '.txt', 'w')\n\tatexit.register(lambda : sys.stdout.close())\n(N,) = getIntList()\nzz = ((1, -1), (0, 2), (1, -1))\nnow = (0, 0)\nfor i in range(N):\n\tprint(now[0], now[1])\n\tnow = (now[0] + zz[i % 3][0], now[1] + zz[i % 3][1])\n", "gcd = lambda a, b: gcd(b, a % b) if b else a\n\ndef main():\n\tn = int(input())\n\tif n == 1:\n\t\tprint(0, 0)\n\t\treturn\n\tx = 2 * n // 3\n\tif 2 * n % 2:\n\t\tx += 1\n\ts = 0\n\tfor i in range(x):\n\t\tprint(i, 0)\n\t\ts += 1\n\tfor j in range(1, x, 2):\n\t\tprint(j, 3)\n\t\ts += 1\n\twhile n - s:\n\t\ts += 1\n\t\ti += 1\n\t\tprint(i, 0)\nmain()\n", "n = int(input())\nabove = n // 3\nbelow = n - above\nfor i in range(above):\n\tprint(2 * i + 1, 3)\nfor i in range(below):\n\tprint(i, 0)\n", "n = int(input())\ntop = n // 3\nfor i in range(top):\n\tx = 1 + 2 * i\n\tprint(str(x) + ' 3')\nbot = n - top\nfor i in range(bot):\n\tprint(str(i) + ' 0')\n", "from sys import exit\nn = int(input())\nif n <= 10:\n\tfor i in range(n):\n\t\tprint(0, i)\n\texit()\nprint(0, 0)\nfor i in range(4, n + 1, 3):\n\tk = i // 3 * 2\n\tprint(k, 0)\n\tprint(k - 1, 1)\n\tprint(k - 2, 2)\nk = (n + 1) // 3 * 2\nif n % 3 == 0:\n\tprint(k - 1, 1)\n\tprint(k - 2, 2)\nelif n % 3 == 2:\n\tprint(k - 2, 2)\n", "n = int(input())\nanss = [(0, 0)]\nfor i in range(1, n):\n\tanss.append((0, i))\n\tanss.append((i, 0))\n\tanss.append((0, -i))\n\tanss.append((-i, 0))\nfor i in range(n):\n\tprint(str(anss[i][0]) + ' ' + str(anss[i][1]))\n", "for i in range(int(input())):\n\tprint(2 * i // 3, 2 * i % 3)\n", "from itertools import *\nmoves = [(x * mx, y * my) for (mx, my, (x, y)) in product((-1, 1), (-1, 1), ((1, 2), (2, 1)))]\n\ndef ac(l, x):\n\tif l == 0:\n\t\treturn 0\n\treturn l[x] if 0 <= x < len(l) else 0\n\ndef work():\n\tx = 1\n\twhile x:\n\t\tx = 0\n\t\tfor r in range(len(a)):\n\t\t\tfor c in range(len(a[0])):\n\t\t\t\tif not a[r][c] and sum((ac(ac(a, r + dr), c + dc) for (dr, dc) in moves)) >= 4:\n\t\t\t\t\ta[r][c] = 1\n\t\t\t\t\tx = 1\nfor n in [int(input())]:\n\tcand = set()\n\tfor i in range(1000):\n\t\tfor (x, y) in ((0, i), (i, 0), (i, 1), (-i, 0), (-i, 1), (0, -i)):\n\t\t\tif x == 0 or x % 3 != 1:\n\t\t\t\tif n == len(cand):\n\t\t\t\t\tbreak\n\t\t\t\tcand.add((x, y))\n\tassert len(cand) == n\n\tfor (x, y) in cand:\n\t\tprint(x, y)\n", "print('\\n'.join((str(2 * i // 3) + ' ' + str(2 * i % 3) for i in range(int(input())))))\n", "n = int(input())\nk = n // 3\nans = []\nfor i in range(k):\n\tans += [(0, 2 * i)]\n\tans += [(1, 2 * i + 1)]\n\tans += [(2, 2 * i)]\nfor i in range(n % 3):\n\tans += [(-1000, -1000 + i)]\nres = ''\nfor i in ans:\n\tres += ' '.join(map(str, i)) + '\\n'\nprint(res)\n", "n = int(input())\nctr = i = 0\nwhile ctr < n:\n\tprint(i, 0)\n\tctr += 1\n\tif i % 2 and ctr < n:\n\t\tprint(i, 3)\n\t\tctr += 1\n\ti += 1\n", "n = int(input())\nprint('0 0')\nn -= 1\nk = n // 2\np = n - k\nx = -k // 2\nwhile k > 0:\n\tif x != 0:\n\t\tprint(x, 0)\n\t\tk -= 1\n\tx += 1\ny = -p // 2\nwhile p > 0:\n\tif y != 0:\n\t\tprint(0, y)\n\t\tp -= 1\n\ty += 1\n", "n = int(input())\nfor i in range(n // 3):\n\tprint(-2, 1 + i * 2)\nfor i in range(n - n // 3):\n\tprint(1, i)\n"]

source: codeforces

raw_problem:
C. Knights

time limit per test
1 second

memory limit per test
256 megabytes

input
standard input

output
standard output

Ivan places knights on infinite chessboard. Initially there are $$$n$$$ knights. If there is free cell which is under attack of at least $$$4$$$ knights then he places new knight in this cell. Ivan repeats this until there are no such free cells. One can prove that this process is finite. One can also prove that position in the end does not depend on the order in which new knights are placed.

Ivan asked you to find initial placement of exactly $$$n$$$ knights such that in the end there will be at least $$$\lfloor \frac{n^{2}}{10} \rfloor$$$ knights.

Input

The only line of input contains one integer $$$n$$$ ($$$1 \le n \le 10^{3}$$$) — number of knights in the initial placement.

Output

Print $$$n$$$ lines. Each line should contain $$$2$$$ numbers $$$x_{i}$$$ and $$$y_{i}$$$ ($$$-10^{9} \le x_{i}, \,\, y_{i} \le 10^{9}$$$) — coordinates of $$$i$$$-th knight. For all $$$i \ne j$$$, $$$(x_{i}, \,\, y_{i}) \ne (x_{j}, \,\, y_{j})$$$ should hold. In other words, all knights should be in different cells.

It is guaranteed that the solution exists.

Examples

Input

4

Output

1 1
3 1
1 5
4 4

Input

7

Output

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

Note

Let's look at second example:

Green zeroes are initial knights. Cell $$$(3, \,\, 3)$$$ is under attack of $$$4$$$ knights in cells $$$(1, \,\, 2)$$$, $$$(2, \,\, 1)$$$, $$$(4, \,\, 1)$$$ and $$$(5, \,\, 2)$$$, therefore Ivan will place a knight in this cell. Cell $$$(4, \,\, 5)$$$ is initially attacked by only $$$3$$$ knights in cells $$$(2, \,\, 6)$$$, $$$(5, \,\, 7)$$$ and $$$(6, \,\, 6)$$$. But new knight in cell $$$(3, \,\, 3)$$$ also attacks cell $$$(4, \,\, 5)$$$, now it is attacked by $$$4$$$ knights and Ivan will place another knight in this cell. There are no more free cells which are attacked by $$$4$$$ or more knights, so the process stops. There are $$$9$$$ knights in the end, which is not less than $$$\lfloor \frac{7^{2}}{10} \rfloor = 4$$$.

question:
Ivan places knights on infinite chessboard. Initially there are $$$n$$$ knights. If there is free cell which is under attack of at least $$$4$$$ knights then he places new knight in this cell. Ivan repeats this until there are no such free cells. One can prove that this process is finite. One can also prove that position in the end does not depend on the order in which new knights are placed.
Ivan asked you to find initial placement of exactly $$$n$$$ knights such that in the end there will be at least $$$\lfloor \frac{n^{2}}{10} \rfloor$$$ knights.

Input
The only line of input contains one integer $$$n$$$ ($$$1 \le n \le 10^{3}$$$) — number of knights in the initial placement.

Output
Print $$$n$$$ lines. Each line should contain $$$2$$$ numbers $$$x_{i}$$$ and $$$y_{i}$$$ ($$$-10^{9} \le x_{i}, \,\, y_{i} \le 10^{9}$$$) — coordinates of $$$i$$$-th knight. For all $$$i \ne j$$$, $$$(x_{i}, \,\, y_{i}) \ne (x_{j}, \,\, y_{j})$$$ should hold. In other words, all knights should be in different cells.
It is guaranteed that the solution exists.

Examples
Input
4

Output
1 1
3 1
1 5
4 4

Input
7

Output
2 1
1 2
4 1
5 2
2 6
5 7
6 6

Note
Let's look at second example:
![image](1.png)
Green zeroes are initial knights. Cell $$$(3, \,\, 3)$$$ is under attack of $$$4$$$ knights in cells $$$(1, \,\, 2)$$$, $$$(2, \,\, 1)$$$, $$$(4, \,\, 1)$$$ and $$$(5, \,\, 2)$$$, therefore Ivan will place a knight in this cell. Cell $$$(4, \,\, 5)$$$ is initially attacked by only $$$3$$$ knights in cells $$$(2, \,\, 6)$$$, $$$(5, \,\, 7)$$$ and $$$(6, \,\, 6)$$$. But new knight in cell $$$(3, \,\, 3)$$$ also attacks cell $$$(4, \,\, 5)$$$, now it is attacked by $$$4$$$ knights and Ivan will place another knight in this cell. There are no more free cells which are attacked by $$$4$$$ or more knights, so the process stops. There are $$$9$$$ knights in the end, which is not less than $$$\lfloor \frac{7^{2}}{10} \rfloor = 4$$$.

Expected Time Complexity: O(N)

data_split: test


Rectangle Game

source: Waseda University Programming Contest 2020

raw_problem:
Problem K: Rectangle Game

Problem

    $N \times M$ のマス目が与えられます。

    ミクさんとルカさんはこのマス目と、整数 $Z$ を使ってゲームをします。ミクさんから始め、交互に以下の操作を繰り返します。

        前回相手が選んだ整数を $p$ として、 $p \leqq x$ を満たすような整数 $x$ を選ぶ。

        ただし最初の先攻の操作においては、 $1 \leqq x \leqq Z$ を満たす整数 $x$ を選ぶ。

        $1 \times x$ の長方形を、いくつかのマス目の上に置く。

        このとき、長方形を回転させてもよいが、以下の条件を満たすように置く必要がある。

長方形が他の長方形と重なってはならない。

長方形はマス目全体をはみ出してはならない。

$1 \times x$ の長方形は、ちょうど $x$ 個のマスを完全に覆う。

    長方形を置けなくなった人が負けです。

    2人が最適に行動するとき、どちらが勝つか判定してください。

Constraints

入力は以下の条件を満たす。

$1 \leqq N, M \leqq 10^{6}$

$1 \leqq Z \leqq \max (N, M)$

入力は全て整数である。

Input

入力は以下の形式で与えられる。

    $N$ $M$ $Z$

    1行目に整数 $N$ $M$ $Z$ が空白区切りで与えられる。

Output

    先手のミクさんが勝つとき"FIRST"、後手のルカさんが勝つとき"SECOND"と出力してください。

    英大文字で出力することに注意してください。また、末尾に改行を出力するのを忘れないようにしてください。

Sample Input 1

2 2 2

Sample Output 1

SECOND

    ミクさんの置く長方形をA、ルカさんの置く長方形をBとします。

    ミクさんがどのように長方形を置いても、次にルカさんが以下の図の様に長方形を置くことでルカさんが勝利します。

Sample Input 2

3 6 4

Sample Output 2

FIRST

solutions: ["import sys\ninput = lambda : sys.stdin.readline().rstrip()\nsys.setrecursionlimit(max(1000, 10**9))\nwrite = lambda x: sys.stdout.write(x+\"\\n\")\n\n\nn,m,z = list(map(int, input().split()))\nif n%2==0 and m%2==0:\n    print(\"SECOND\")\nelif n%2==1 and m%2==1:\n    print(\"FIRST\")\nelse:\n    if z>=2:\n        print(\"FIRST\")\n    else:\n        print(\"SECOND\")\n", "N,M,L=map(int,input().split())\nif (N&1)==0 and (M&1)==0:\n  print('SECOND')\nelse:\n  if (N&1)+(M&1)==1 and L==1:\n    print('SECOND')\n  else:\n    print('FIRST')\n", "n, m, z = map(int, input().split())\n\n\nif n % 2 == 1 and m % 2 == 1:\n    print(\"FIRST\")\nelif n % 2 == 0 and m % 2 == 0:\n    print(\"SECOND\")\nelse:\n    if z == 1:\n        print(\"SECOND\")\n    else:\n        print(\"FIRST\")\n"]

source: aizu

question:
Problem K: Rectangle Game

Problem

A grid of $N \times M$ is given. Miku and Luka will use this grid and an integer $Z$ to play a game. Starting with Miku, they will take turns repeating the following actions:

- Choose an integer $x$ such that $p \leqq x$, where $p$ is the integer chosen by the opponent in the previous turn. However, for the first turn, choose an integer $x$ such that $1 \leqq x \leqq Z$.

- Place a $1 \times x$ rectangle on top of some of the grid squares. The rectangle may be rotated, but it must be placed according to the following conditions:

   - Rectangles cannot overlap with other rectangles.
   - Rectangles cannot extend beyond the entirety of the grid.
   - A $1 \times x$ rectangle must cover exactly $x$ grid squares.

The person who can no longer place a rectangle loses. Please determine who will win when both play optimally.

Constraints
The input satisfies the following conditions:

- $1 \leqq N, M \leqq 10^{6}$
- $1 \leqq Z \leqq \max (N, M)$
- All inputs are integers.

Input
The input is given in the following format:

$N$ $M$ $Z$

The first line contains integers $N$, $M$, $Z$ separated by spaces.

Output

If Miku (the first player) wins, output "FIRST". If Luka (the second player) wins, output "SECOND". Note that the output should be in capital letters. Also, do not forget to output a newline at the end.

Sample Input 1

2 2 2

Sample Output 1

SECOND

Miku's rectangles are labeled as A, Luka's as B.
Regardless of how Miku places a rectangle, Luka will win by placing a rectangle as shown in the figures below.

![image](1.png)
![image](2.png)
Sample Input 2

3 6 4

Sample Output 2

FIRST

image_tags: Chessboard Chessboard

data_split: test


F. Tree with Maximum Cost

problem_index: F

time_limit: 2 seconds

memory_limit: 256 megabytes

note:
Picture corresponding to the first example: ![image](images/cf_1092_F/1.png)
You can choose the vertex $$$3$$$ as a root, then the answer will be $$$2 \cdot 9 + 1 \cdot 4 + 0 \cdot 1 + 3 \cdot 7 + 3 \cdot 10 + 4 \cdot 1 + 4 \cdot 6 + 4 \cdot 5 = 18 + 4 + 0 + 21 + 30 + 4 + 24 + 20 = 121$$$.
In the second example tree consists only of one vertex so the answer is always $$$0$$$.

solutions: ["from sys import stdin, setrecursionlimit\nn = int(stdin.readline())\nay = [int(x) for x in stdin.readline().split()]\ngraph = [set() for x in range(n)]\nfor e in range(n - 1):\n\t(a, b) = [int(x) - 1 for x in stdin.readline().split()]\n\tgraph[a].add(b)\n\tgraph[b].add(a)\ndists = {}\nchild = {}\nbruh = sum(ay)\npath = [(0, 0)]\nfor (x, p) in path:\n\tfor y in graph[x]:\n\t\tif y != p:\n\t\t\tpath.append((y, x))\nfor (x, parent) in path[::-1]:\n\ttotal = 0\n\tchildren = ay[x]\n\tfor v in graph[x]:\n\t\tif v != parent:\n\t\t\t(c, sm) = (child[v], dists[v])\n\t\t\tchildren += c\n\t\t\ttotal += sm + c\n\tdists[x] = total\n\tchild[x] = children\n(b2, b3) = (child[0], dists[0])\nfor (x, parent) in path:\n\tfor v in graph[x]:\n\t\tif v != parent:\n\t\t\tdists[v] = dists[x] + bruh - child[v] * 2\nprint(max([dists[y] for y in range(n)]))\n", "import sys\nfrom collections import deque\nfrom types import GeneratorType\nsys.setrecursionlimit(200000)\ninput = sys.stdin.readline\n\ndef bootstrap(f, stack=[]):\n\n\tdef wrappedfunc(*args, **kwargs):\n\t\tif stack:\n\t\t\treturn f(*args, **kwargs)\n\t\telse:\n\t\t\tto = f(*args, **kwargs)\n\t\t\twhile True:\n\t\t\t\tif type(to) is GeneratorType:\n\t\t\t\t\tstack.append(to)\n\t\t\t\t\tto = next(to)\n\t\t\t\telse:\n\t\t\t\t\tstack.pop()\n\t\t\t\t\tif not stack:\n\t\t\t\t\t\tbreak\n\t\t\t\t\tto = stack[-1].send(to)\n\t\t\treturn to\n\treturn wrappedfunc\nn = int(input())\nval = [int(i) for i in input().split()]\ntree = [[] for i in range(n + 1)]\ndp = [0 for i in range(n + 1)]\ns = [0 for i in range(n + 1)]\nans = [0 for i in range(n + 1)]\nfor i in range(n - 1):\n\t(a, b) = map(int, input().split())\n\ttree[a].append(b)\n\ttree[b].append(a)\n\n@bootstrap\ndef dfs1(node, dist, pd):\n\tfor child in tree[node]:\n\t\tif child == pd:\n\t\t\tcontinue\n\t\tyield dfs1(child, dist + 1, node)\n\t\tdp[node] += dp[child]\n\t\ts[node] += s[child]\n\tdp[node] += val[node - 1] * dist\n\ts[node] += val[node - 1]\n\tyield dp[node]\ndfs1(1, 0, 1)\nq = deque()\nans[1] = dp[1]\nfor node in tree[1]:\n\tq.append((node, 1))\nwhile len(q) > 0:\n\t(node, pd) = q.popleft()\n\tsub_dp = ans[pd] - (dp[node] + s[node])\n\tadded = s[1] - s[node]\n\tans[node] = sub_dp + added + dp[node]\n\tfor child in tree[node]:\n\t\tif child == pd:\n\t\t\tcontinue\n\t\tq.append((child, node))\nprint(max(ans))\n", "import traceback\nimport sys\nsys.setrecursionlimit(200010)\ntry:\n\tn = int(input())\n\ta = [0]\n\ta.extend(list(map(int, input().split())))\n\tD = [[] for i in range(n + 1)]\n\tfor i in range(n - 1):\n\t\t(e1, e2) = map(int, input().split())\n\t\tD[e1].append(e2)\n\t\tD[e2].append(e1)\n\tvisited = [False for i in range(n + 1)]\n\tcost = [a[i] for i in range(n + 1)]\n\tparent = [0 for i in range(n + 1)]\n\tval = 0\n\n\tdef dfs(s, depth):\n\t\tglobal visited\n\t\tglobal cost\n\t\tglobal val\n\t\tglobal a\n\t\tglobal D\n\t\tstack = [(s, depth)]\n\t\twhile stack:\n\t\t\t(s, depth) = stack[-1]\n\t\t\tif visited[s]:\n\t\t\t\tstack.pop()\n\t\t\t\tcost[parent[s]] += cost[s]\n\t\t\t\tcontinue\n\t\t\telse:\n\t\t\t\tvisited[s] = True\n\t\t\t\tval += depth * a[s]\n\t\t\tfor i in D[s]:\n\t\t\t\tif not visited[i]:\n\t\t\t\t\tparent[i] = s\n\t\t\t\t\tstack.append((i, depth + 1))\n\tdfs(1, 0)\n\tmax_cost = val\n\tvisited = [False for i in range(n + 1)]\n\tcost[0] = sum(a)\n\n\tdef trav(s, some_val):\n\t\tglobal cost\n\t\tglobal visited\n\t\tglobal max_cost\n\t\tglobal D\n\t\tstack = [(s, some_val)]\n\t\twhile stack:\n\t\t\t(s, some_val) = stack.pop()\n\t\t\tvisited[s] = True\n\t\t\tif some_val > max_cost:\n\t\t\t\tmax_cost = some_val\n\t\t\tfor i in D[s]:\n\t\t\t\tif not visited[i]:\n\t\t\t\t\tstack.append((i, some_val + (cost[0] - cost[i]) - cost[i]))\n\ttrav(1, val)\n\tprint(max_cost)\nexcept Exception as ex:\n\ttraceback.print_tb(ex.__traceback__)\n\tprint(ex)\n", "import os\nimport sys\nfrom io import BytesIO, IOBase\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nfrom math import factorial\nfrom collections import Counter, defaultdict, deque\nfrom heapq import heapify, heappop, heappush\n\ndef RL():\n\treturn map(int, sys.stdin.readline().rstrip().split())\n\ndef RLL():\n\treturn list(map(int, sys.stdin.readline().rstrip().split()))\n\ndef N():\n\treturn int(input())\n\ndef comb(n, m):\n\treturn factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0\n\ndef perm(n, m):\n\treturn factorial(n) // factorial(n - m) if n >= m else 0\n\ndef mdis(x1, y1, x2, y2):\n\treturn abs(x1 - x2) + abs(y1 - y2)\nmod = 998244353\nINF = float('inf')\n\ndef main():\n\tn = N()\n\tarr = [0] + RLL()\n\tgp = [[] for _ in range(n + 1)]\n\tfor _ in range(n - 1):\n\t\t(f, t) = RL()\n\t\tgp[f].append(t)\n\t\tgp[t].append(f)\n\tq = [(1, 0, 0)]\n\tpar = [0] * (n + 1)\n\tnow = 0\n\trec = [0] * (n + 1)\n\tsm = [0] * (n + 1)\n\twhile q:\n\t\t(nd, st, dp) = q.pop()\n\t\tif st == 0:\n\t\t\tnow += 1\n\t\t\tq.append((nd, 1, dp))\n\t\t\tfor nex in gp[nd]:\n\t\t\t\tif nex == par[nd]:\n\t\t\t\t\tcontinue\n\t\t\t\tpar[nex] = nd\n\t\t\t\tq.append((nex, 0, dp + 1))\n\t\telse:\n\t\t\trec[nd] += dp * arr[nd]\n\t\t\trec[par[nd]] += rec[nd]\n\t\t\tsm[nd] += arr[nd]\n\t\t\tsm[par[nd]] += sm[nd]\n\tq = [(1, 0)]\n\tres = rec[1]\n\tret = res\n\twhile q:\n\t\t(nd, st) = q.pop()\n\t\tif st == 0:\n\t\t\tif nd != 1:\n\t\t\t\tres -= sm[nd]\n\t\t\t\tres += sm[par[nd]] - sm[nd]\n\t\t\t\tsm[par[nd]] -= sm[nd]\n\t\t\t\tsm[nd] += sm[par[nd]]\n\t\t\t\tret = max(res, ret)\n\t\t\tq.append((nd, 1))\n\t\t\tfor nex in gp[nd]:\n\t\t\t\tif nex == par[nd]:\n\t\t\t\t\tcontinue\n\t\t\t\tq.append((nex, 0))\n\t\telif nd != 1:\n\t\t\tsm[nd] -= sm[par[nd]]\n\t\t\tsm[par[nd]] += sm[nd]\n\t\t\tres -= sm[par[nd]] - sm[nd]\n\t\t\tres += sm[nd]\n\tprint(ret)\nmain()\n", "import io, os\nfrom collections import deque\ninput = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline\n\nclass Node:\n\n\tdef __init__(self, val):\n\t\tself.val = int(val)\n\t\tself.cul = 0\n\t\tself.child = set()\n\t\tself.path = {}\n\n\tdef __str__(self):\n\t\treturn f'{self.val} {self.child} {self.path}'\nn = int(input())\na = list(map(Node, input().split()))\nsu = 0\nfor i in a:\n\tsu += i.val\nfor _ in range(n - 1):\n\t(u, v) = map(int, input().split())\n\ta[u - 1].child.add(v)\n\ta[v - 1].child.add(u)\nst = [1]\nwhile len(st):\n\tx = st[-1]\n\tif not len(a[x - 1].child):\n\t\tcurr = a[st.pop() - 1].val + a[x - 1].cul\n\t\tif len(st):\n\t\t\ta[x - 1].path[st[-1]] = su - a[x - 1].val - sum(a[x - 1].path.values())\n\t\t\ta[st[-1] - 1].path[x] = curr\n\t\t\ta[st[-1] - 1].cul += curr\n\telse:\n\t\ty = a[x - 1].child.pop()\n\t\ta[y - 1].child.remove(x)\n\t\tst.append(y)\n(curr, visi, ans) = (deque([1]), {1}, 0)\nwhile len(curr):\n\tx = curr.popleft()\n\tfor y in a[x - 1].path:\n\t\tif y not in visi:\n\t\t\tans += a[x - 1].path[y]\n\t\t\tvisi.add(y)\n\t\t\tcurr.append(y)\n(maxi, val) = (ans, [0] * n)\nval[0] = ans\n(curr, visi) = (deque([1]), {1})\nwhile len(curr):\n\tx = curr.popleft()\n\tfor y in a[x - 1].path:\n\t\tif y not in visi:\n\t\t\tval[y - 1] = val[x - 1] - a[x - 1].path[y] + a[y - 1].path[x]\n\t\t\tmaxi = max(maxi, val[y - 1])\n\t\t\tvisi.add(y)\n\t\t\tcurr.append(y)\nprint(maxi)\n", "from collections import defaultdict\nimport sys, threading\n\ndef work():\n\tsys.setrecursionlimit(1 << 18)\n\n\tdef fun(u, level, p):\n\t\tl[1] += level * arr[u - 1]\n\t\tsumm[u] = arr[u - 1]\n\t\tfor i in graph[u]:\n\t\t\tif i != p:\n\t\t\t\tfun(i, level + 1, u)\n\t\t\t\tsumm[u] += summ[i]\n\n\tdef fun2(u, p):\n\t\tfor i in graph[u]:\n\t\t\tif i != p:\n\t\t\t\tl[i] = l[u] + s - 2 * summ[i]\n\t\t\t\tfun2(i, u)\n\tn = int(input())\n\tn1 = n\n\tarr = [int(x) for x in input().split()]\n\tgraph = defaultdict(list)\n\twhile n1 - 1:\n\t\tn1 -= 1\n\t\t(u, v) = [int(x) for x in input().split()]\n\t\tgraph[u].append(v)\n\t\tgraph[v].append(u)\n\ts = 0\n\tfor i in arr:\n\t\ts += i\n\tsumm = [0] * (n + 1)\n\tl = [0] * (n + 1)\n\tfun(1, 0, 0)\n\tfun2(1, 0)\n\tprint(max(l))\nsys.setrecursionlimit(200050)\nthreading.stack_size(80000000)\nthread = threading.Thread(target=work)\nthread.start()\n", "from functools import *\nfrom operator import *\nimport sys, threading\n\ndef work():\n\tsys.setrecursionlimit(1 << 18)\n\tn = int(input())\n\ta = [0] + list(map(int, input().split()))\n\ttota = sum(a)\n\tadj = [[] for _ in range(n + 1)]\n\ttotsz = [0] * (n + 1)\n\ttotw = [0] * (n + 1)\n\n\tdef dfs(u, p):\n\t\ttotsz[u] = a[u]\n\t\tfor v in adj[u]:\n\t\t\tif v == p:\n\t\t\t\tcontinue\n\t\t\tdfs(v, u)\n\t\t\ttotsz[u] += totsz[v]\n\t\t\ttotw[u] += totw[v] + totsz[v]\n\n\tdef dfs2(u, p, w):\n\t\ttotw[u] += w\n\t\tfor v in adj[u]:\n\t\t\tif v == p:\n\t\t\t\tcontinue\n\t\t\tdfs2(v, u, totw[u] - totw[v] - totsz[v] + tota - totsz[v])\n\tfor _ in range(n - 1):\n\t\t(u, v) = list(map(int, input().split()))\n\t\tadj[u].append(v)\n\t\tadj[v].append(u)\n\tdfs(1, 0)\n\tdfs2(1, 0, 0)\n\tprint(max(totw))\n\ndef __starting_point():\n\tsys.setrecursionlimit(200050)\n\tthreading.stack_size(80000000)\n\tthread = threading.Thread(target=work)\n\tthread.start()\n__starting_point()\n", "import os\nimport sys\nfrom io import BytesIO, IOBase\nfrom types import GeneratorType\nfrom collections import defaultdict\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nsys.setrecursionlimit(2 * 10 ** 5)\nans = 0\n\ndef bootstrap(f, stack=[]):\n\n\tdef wrappedfunc(*args, **kwargs):\n\t\tif stack:\n\t\t\treturn f(*args, **kwargs)\n\t\telse:\n\t\t\tto = f(*args, **kwargs)\n\t\t\twhile True:\n\t\t\t\tif type(to) is GeneratorType:\n\t\t\t\t\tstack.append(to)\n\t\t\t\t\tto = next(to)\n\t\t\t\telse:\n\t\t\t\t\tstack.pop()\n\t\t\t\t\tif not stack:\n\t\t\t\t\t\tbreak\n\t\t\t\t\tto = stack[-1].send(to)\n\t\t\treturn to\n\treturn wrappedfunc\n\n@bootstrap\ndef dfs(now, lay, fa):\n\tSUM[now] = 0\n\tNUM[now] = C[now]\n\tfor to in A[now]:\n\t\tif to != fa:\n\t\t\tyield dfs(to, lay + 1, now)\n\t\t\tSUM[now] += SUM[to]\n\t\t\tSUM[now] += NUM[to]\n\t\t\tNUM[now] += NUM[to]\n\tyield\n\n@bootstrap\ndef change(now, fa):\n\tglobal ans\n\tans = max(ans, SUM[now])\n\tfor to in A[now]:\n\t\tif to != fa:\n\t\t\tSUM[now] -= SUM[to]\n\t\t\tSUM[now] -= NUM[to]\n\t\t\tNUM[now] -= NUM[to]\n\t\t\tNUM[to] += NUM[now]\n\t\t\tSUM[to] += SUM[now]\n\t\t\tSUM[to] += NUM[now]\n\t\t\tyield change(to, now)\n\t\t\tSUM[to] -= SUM[now]\n\t\t\tSUM[to] -= NUM[now]\n\t\t\tNUM[to] -= NUM[now]\n\t\t\tNUM[now] += NUM[to]\n\t\t\tSUM[now] += SUM[to]\n\t\t\tSUM[now] += NUM[to]\n\tyield\nn = int(input())\nA = [[] for i in range(n + 1)]\nC = [0] + list(map(int, input().split()))\nNUM = [0] * (n + 1)\nSUM = [0] * (n + 1)\nfor i in range(n - 1):\n\t(x, y) = map(int, input().split())\n\tA[x].append(y)\n\tA[y].append(x)\ndfs(1, 0, 0)\nchange(1, 0)\nprint(ans)\n", "import os\nimport sys\nfrom io import BytesIO, IOBase\nfrom types import GeneratorType\nfrom collections import defaultdict\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nsys.setrecursionlimit(2 * 10 ** 5)\n\ndef bootstrap(f, stack=[]):\n\n\tdef wrappedfunc(*args, **kwargs):\n\t\tif stack:\n\t\t\treturn f(*args, **kwargs)\n\t\telse:\n\t\t\tto = f(*args, **kwargs)\n\t\t\twhile True:\n\t\t\t\tif type(to) is GeneratorType:\n\t\t\t\t\tstack.append(to)\n\t\t\t\t\tto = next(to)\n\t\t\t\telse:\n\t\t\t\t\tstack.pop()\n\t\t\t\t\tif not stack:\n\t\t\t\t\t\tbreak\n\t\t\t\t\tto = stack[-1].send(to)\n\t\t\treturn to\n\treturn wrappedfunc\n\n@bootstrap\ndef dfs(u, p):\n\tfor j in adj[u]:\n\t\tif j != p:\n\t\t\tyield dfs(j, u)\n\t\t\tf[u] += f[j] + res[j]\n\t\t\tres[u] += res[j]\n\tres[u] += b[u - 1]\n\tyield\n\n@bootstrap\ndef dfs2(u, p, val):\n\tfor j in adj[u]:\n\t\tif j != p:\n\t\t\tyield dfs2(j, u, f[u] - (f[j] + res[j]) + val + (s - res[u]))\n\tans[u] = f[u] + val + (s - res[u])\n\tyield\nn = int(input())\nb = list(map(int, input().split()))\ns = sum(b)\nadj = [[] for i in range(n + 1)]\nfor j in range(n - 1):\n\t(u, v) = map(int, input().split())\n\tadj[u].append(v)\n\tadj[v].append(u)\nf = [0] * (n + 1)\nres = [0] * (n + 1)\ndfs(1, 0)\nans = [0] * (n + 1)\ndfs2(1, 0, 0)\nprint(max(ans[1:]))\n", "from __future__ import division, print_function\nfrom fractions import Fraction\nimport sys\nimport os\nfrom io import BytesIO, IOBase\nfrom itertools import *\nimport bisect\nfrom heapq import *\nfrom math import *\nfrom copy import *\nfrom collections import deque\nfrom collections import Counter as counter\nfrom itertools import combinations as comb\nfrom itertools import permutations as permutate\nfrom bisect import bisect_left as bl\nfrom bisect import bisect_right as br\nfrom bisect import bisect\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n\ndef print(*args, **kwargs):\n\t(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))\n\tat_start = True\n\tfor x in args:\n\t\tif not at_start:\n\t\t\tfile.write(sep)\n\t\tfile.write(str(x))\n\t\tat_start = False\n\tfile.write(kwargs.pop('end', '\\n'))\n\tif kwargs.pop('flush', False):\n\t\tfile.flush()\nif sys.version_info[0] < 3:\n\t(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))\nelse:\n\t(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\nfrom types import GeneratorType\n\ndef iterative(f, stack=[]):\n\n\tdef wrapped_func(*args, **kwargs):\n\t\tif stack:\n\t\t\treturn f(*args, **kwargs)\n\t\tto = f(*args, **kwargs)\n\t\twhile True:\n\t\t\tif type(to) is GeneratorType:\n\t\t\t\tstack.append(to)\n\t\t\t\tto = next(to)\n\t\t\t\tcontinue\n\t\t\tstack.pop()\n\t\t\tif not stack:\n\t\t\t\tbreak\n\t\t\tto = stack[-1].send(to)\n\t\treturn to\n\treturn wrapped_func\nmod = 1000000007\n\ndef inp():\n\treturn sys.stdin.readline().rstrip('\\r\\n')\n\ndef out(var):\n\tsys.stdout.write(str(var))\n\ndef lis():\n\treturn list(map(int, inp().split()))\n\ndef stringlis():\n\treturn list(map(str, inp().split()))\n\ndef sep():\n\treturn map(int, inp().split())\n\ndef strsep():\n\treturn map(str, inp().split())\n\ndef zerolist(n):\n\treturn [0] * n\n\ndef nextline():\n\tout('\\n')\n\ndef testcase(t):\n\tfor pp in range(t):\n\t\tsolve(pp)\n\ndef printlist(a):\n\tfor p in range(0, len(a)):\n\t\tout(str(a[p]) + ' ')\n\ndef google(p):\n\tprint('Case #' + str(p) + ': ', end='')\n\ndef lcm(a, b):\n\treturn a * b // gcd(a, b)\n\ndef power(x, y, p):\n\tres = 1\n\tx = x % p\n\tif x == 0:\n\t\treturn 0\n\twhile y > 0:\n\t\tif y & 1 == 1:\n\t\t\tres = res * x % p\n\t\ty = y >> 1\n\t\tx = x * x % p\n\treturn res\n\ndef ncr(n, r):\n\treturn factorial(n) // (factorial(r) * factorial(max(n - r, 1)))\n\ndef isPrime(n):\n\tif n <= 1:\n\t\treturn False\n\tif n <= 3:\n\t\treturn True\n\tif n % 2 == 0 or n % 3 == 0:\n\t\treturn False\n\ti = 5\n\twhile i * i <= n:\n\t\tif n % i == 0 or n % (i + 2) == 0:\n\t\t\treturn False\n\t\ti = i + 6\n\treturn True\n\n@iterative\ndef dfs(v, visited, st, sum, par):\n\tvisited[st] = 1\n\tfor i in v[st]:\n\t\tif visited[i] == 0:\n\t\t\tok = (yield dfs(v, visited, i, sum, par))\n\t\t\tpar[i] = st\n\t\t\tsum[st] += sum[i]\n\tyield True\n\ndef bfs(g, st):\n\tvisited = [-1] * len(g)\n\tvisited[st] = 0\n\tqueue = deque([])\n\tqueue.append(st)\n\tnew = []\n\twhile len(queue) != 0:\n\t\ts = queue.popleft()\n\t\tnew.append(s)\n\t\tfor i in g[s]:\n\t\t\tif visited[i] == -1:\n\t\t\t\tvisited[i] = visited[s] + 1\n\t\t\t\tqueue.append(i)\n\treturn visited\n\ndef solve(case):\n\tn = int(inp())\n\tval = lis()\n\tg = [[] for i in range(n)]\n\tfor i in range(n - 1):\n\t\t(a, b) = sep()\n\t\ta -= 1\n\t\tb -= 1\n\t\tg[a].append(b)\n\t\tg[b].append(a)\n\ta = deepcopy(val)\n\tvis = [False] * n\n\tpar = [-1] * n\n\tdfs(g, vis, 0, val, par)\n\tcurrans = 0\n\tdist = bfs(g, 0)\n\tfor i in range(n):\n\t\tcurrans += a[i] * dist[i]\n\tans = currans\n\tss = sum(a)\n\tq = []\n\tq.append((0, currans))\n\twhile len(q) != 0:\n\t\ts = q.pop()\n\t\tcurrans = s[1]\n\t\ts = s[0]\n\t\tfor i in g[s]:\n\t\t\tif i == par[s]:\n\t\t\t\tcontinue\n\t\t\ttemp = currans - val[i] + (ss - val[i])\n\t\t\tans = max(ans, temp)\n\t\t\tq.append((i, temp))\n\tprint(ans)\ntestcase(1)\n", "import sys\nimport io, os\ninput = sys.stdin.buffer.readline\nn = int(input())\nA = list(map(int, input().split()))\ng = [[] for _ in range(n)]\nfor i in range(n - 1):\n\t(u, v) = map(int, input().split())\n\t(u, v) = (u - 1, v - 1)\n\tg[u].append(v)\n\tg[v].append(u)\ns = []\ns.append(0)\nparent = [-1] * n\ndist = [0] * n\norder = []\nwhile s:\n\tv = s.pop()\n\torder.append(v)\n\tfor u in g[v]:\n\t\tif u == parent[v]:\n\t\t\tcontinue\n\t\tparent[u] = v\n\t\tdist[u] = dist[v] + 1\n\t\ts.append(u)\norder.reverse()\ndp = [0] * n\nres = 0\nfor v in order:\n\tdp[v] += A[v]\n\tres += A[v] * dist[v]\n\tif parent[v] != -1:\n\t\tdp[parent[v]] += dp[v]\nans = [0] * n\nans[0] = res\nfor v in reversed(order):\n\tfor u in g[v]:\n\t\tif u == parent[v]:\n\t\t\tcontinue\n\t\tres = ans[v]\n\t\tres -= dp[u]\n\t\tdp[v] -= dp[u]\n\t\tres += dp[v]\n\t\tans[u] = res\n\t\tdp[v] += dp[u]\n\t\tdp[u] += dp[v] - dp[u]\nprint(max(ans))\n", "from collections import defaultdict\nfrom sys import stdin, setrecursionlimit\nimport threading\ninput = stdin.buffer.readline\n\ndef work():\n\tres = 0\n\tans = 0\n\tsetrecursionlimit(1 << 18)\n\tn = int(input())\n\ta = list(map(int, input().split()))\n\ta.insert(0, 0)\n\tgraph = defaultdict(list)\n\tdist = dict()\n\tfor v in range(n - 1):\n\t\t(a1, b) = map(int, input().split())\n\t\tgraph[a1].append(b)\n\t\tgraph[b].append(a1)\n\n\tdef dfs(v, par, h=0):\n\t\tnonlocal res\n\t\tres += h * a[v]\n\t\tdist[v] = a[v]\n\t\tfor node in graph[v]:\n\t\t\tif node != par:\n\t\t\t\tdfs(node, v, h + 1)\n\t\t\t\tdist[v] += dist[node]\n\n\tdef dfs2(v, par):\n\t\tnonlocal ans, res\n\t\tans = max(ans, res)\n\t\tfor node in graph[v]:\n\t\t\tif node != par:\n\t\t\t\tres -= dist[node]\n\t\t\t\tdist[v] -= dist[node]\n\t\t\t\tres += dist[v]\n\t\t\t\tdist[node] += dist[v]\n\t\t\t\tdfs2(node, v)\n\t\t\t\tdist[node] -= dist[v]\n\t\t\t\tres -= dist[v]\n\t\t\t\tdist[v] += dist[node]\n\t\t\t\tres += dist[node]\n\tdfs(1, -1)\n\tdfs2(1, -1)\n\tprint(ans)\nsetrecursionlimit(300050)\nthreading.stack_size(100000000)\nthread = threading.Thread(target=work)\nthread.start()\n"]

difficulty: HARD

source: codeforces

raw_problem:
F. Tree with Maximum Cost

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

You are given a tree consisting exactly of $$$n$$$ vertices. Tree is a connected undirected graph with $$$n-1$$$ edges. Each vertex $$$v$$$ of this tree has a value $$$a_v$$$ assigned to it.

Let $$$dist(x, y)$$$ be the distance between the vertices $$$x$$$ and $$$y$$$. The distance between the vertices is the number of edges on the simple path between them.

Let's define the cost of the tree as the following value: firstly, let's fix some vertex of the tree. Let it be $$$v$$$. Then the cost of the tree is $$$\sum\limits_{i = 1}^{n} dist(i, v) \cdot a_i$$$.

Your task is to calculate the maximum possible cost of the tree if you can choose $$$v$$$ arbitrarily.

Input

The first line contains one integer $$$n$$$, the number of vertices in the tree ($$$1 \le n \le 2 \cdot 10^5$$$).

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$), where $$$a_i$$$ is the value of the vertex $$$i$$$.

Each of the next $$$n - 1$$$ lines describes an edge of the tree. Edge $$$i$$$ is denoted by two integers $$$u_i$$$ and $$$v_i$$$, the labels of vertices it connects ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$).

It is guaranteed that the given edges form a tree.

Output

Print one integer — the maximum possible cost of the tree if you can choose any vertex as $$$v$$$.

Examples

Input

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

Output

121

Input

1
1337

Output

0

Note

Picture corresponding to the first example:

You can choose the vertex $$$3$$$ as a root, then the answer will be $$$2 \cdot 9 + 1 \cdot 4 + 0 \cdot 1 + 3 \cdot 7 + 3 \cdot 10 + 4 \cdot 1 + 4 \cdot 6 + 4 \cdot 5 = 18 + 4 + 0 + 21 + 30 + 4 + 24 + 20 = 121$$$.

In the second example tree consists only of one vertex so the answer is always $$$0$$$.

question:
You are given a tree consisting exactly of $$$n$$$ vertices. Tree is a connected undirected graph with $$$n-1$$$ edges. Each vertex $$$v$$$ of this tree has a value $$$a_v$$$ assigned to it.
Let $$$dist(x, y)$$$ be the distance between the vertices $$$x$$$ and $$$y$$$. The distance between the vertices is the number of edges on the simple path between them.
Let's define the cost of the tree as the following value: firstly, let's fix some vertex of the tree. Let it be $$$v$$$. Then the cost of the tree is $$$\sum\limits_{i = 1}^{n} dist(i, v) \cdot a_i$$$.
Your task is to calculate the maximum possible cost of the tree if you can choose $$$v$$$ arbitrarily.

Input
The first line contains one integer $$$n$$$, the number of vertices in the tree ($$$1 \le n \le 2 \cdot 10^5$$$).
The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$), where $$$a_i$$$ is the value of the vertex $$$i$$$.
Each of the next $$$n - 1$$$ lines describes an edge of the tree. Edge $$$i$$$ is denoted by two integers $$$u_i$$$ and $$$v_i$$$, the labels of vertices it connects ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$).
It is guaranteed that the given edges form a tree.

Output
Print one integer — the maximum possible cost of the tree if you can choose any vertex as $$$v$$$.

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

Output
121

Input
1
1337

Output
0

Note
Picture corresponding to the first example: ![image](1.png)
You can choose the vertex $$$3$$$ as a root, then the answer will be $$$2 \cdot 9 + 1 \cdot 4 + 0 \cdot 1 + 3 \cdot 7 + 3 \cdot 10 + 4 \cdot 1 + 4 \cdot 6 + 4 \cdot 5 = 18 + 4 + 0 + 21 + 30 + 4 + 24 + 20 = 121$$$.
In the second example tree consists only of one vertex so the answer is always $$$0$$$.

tags: ['Tree algorithms', 'Dynamic programming', 'Graph traversal']

skill_types: ['Dynamic programming']

data_split: test


Cuboid Boat

source: 20th PC Koshien, Final

raw_problem:
直方体ボート

PCK君は直方体の形をしたボートを作っています。PCK君は、このボートのサイズを幅が長さの３分の１、高さが幅の２分の１で、長さ、幅、高さをｃｍ単位で整数にしようと考えています。

このボートに積み荷を載せて水に浮かべます。積み荷を載せたボートが水に浮くのは、ボートと積み荷の重さの合計と、ボートによって押しのけられた水の重さがちょうど釣り合うときです。PCK君はボートの上面と水面が平行になるように、ボートをそっと浮かべます。このとき、ボートの上面から水面までの距離（乾舷、図の実線矢印のところの長さ）を３０ｃｍ以上にしたいと考えているので、そうなるようにボートのサイズを決めなければなりません。

ボートに載せる積み荷の重さが与えられたとき、ボートの長さ、幅、高さがそれぞれ最小何ｃｍになるかを求めるプログラムを作成せよ。ただし、１リットル（＝１０００立方ｃｍ）の水の重さは１キログラム、ボートの重さは大きさにかかわらず５０キログラムとする。

入力

入力は以下の形式で与えられる。

$W$

  １行にボートに載せる積み荷の重さ$W$ ($1 \leq W \leq 1,000$)がキログラム単位の整数で与えられる。

出力

ボートの長さ、幅、高さを、空白区切りで１行にｃｍ単位で出力する。

入出力例

入力例１

300

出力例１

270 90 45

入力例２

500

出力例２

300 100 50

source: aizu

question:
Rectangular Boat

PCK-kun is making a boat in the shape of a rectangular solid. PCK-kun is considering making the size of this boat with a width one-third the length, and the height half the width, with the length, width, and height being integers in cm units.

![image](1.png)

He will load cargo onto this boat and float it on water. The loaded boat floats when the total weight of the boat and the cargo balances exactly with the weight of the water displaced by the boat. PCK-kun will gently float the boat so that the top surface of the boat is parallel to the water surface. At this time, he wants to keep the distance from the top surface of the boat to the water surface (freeboard, the length of the part indicated by the solid arrow in the diagram) at least 30 cm. Therefore, he must determine the size of the boat accordingly.

Create a program to compute the minimum length, width, and height of the boat in cm when the weight of the cargo to be loaded on the boat is given. Assume that the weight of 1 liter (1000 cubic cm) of water is 1 kilogram, and the weight of the boat is 50 kilograms regardless of its size.

Input

Input is given in the following format.

$W$

The weight $W$ ($1 \leq W \leq 1,000$) of the cargo to be loaded on the boat is given as an integer in kilograms on one line.

Output

Output the length, width, and height of the boat in cm units separated by a space on one line.

Input/Output Examples

Input example 1

300

Output example 1

270 90 45

Input example 2

500

Output example 2

300 100 50

data_split: test