F. MCMF?

problem_index: F

time_limit: 3 seconds

memory_limit: 256 megabytes

note:
In the first query, the maximum possible flow is $$$1$$$ i.e one unit from source to $$$2$$$, then one unit from $$$2$$$ to $$$3$$$, then one unit from $$$3$$$ to sink. The cost of the flow is $$$0 \cdot 1 + |2 - 4| \cdot 1 + 0 \cdot 1 = 2$$$.
In the second query, the maximum possible flow is again $$$1$$$ i.e from source to $$$7$$$, $$$7$$$ to $$$6$$$, and $$$6$$$ to sink with a cost of $$$0 \cdot |10 - 10| \cdot 1 + 0 \cdot 1 = 0$$$.
In the third query, the flow network is shown on the left with capacity written over the edge and the cost written in bracket. The image on the right shows the flow through each edge in an optimal configuration.
![image](images/cf_1682_F/1.png)
In the fourth query, the flow network looks as –
![image](images/cf_1682_F/2.png)
The minimum cost maximum flow is achieved in the configuration –
![image](images/cf_1682_F/3.png)
The maximum flow in the above network is 4 and the minimum cost of such flow is 15.

source: codeforces

raw_problem:
F. MCMF?

time limit per test
3 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

You are given two integer arrays $$$a$$$ and $$$b$$$ ($$$b_i \neq 0$$$ and $$$|b_i| \leq 10^9$$$). Array $$$a$$$ is sorted in non-decreasing order.

The cost of a subarray $$$a[l:r]$$$ is defined as follows:

If $$$ \sum\limits_{j = l}^{r} b_j \neq 0$$$, then the cost is not defined.

Otherwise:

 Construct a bipartite flow graph with $$$r-l+1$$$ vertices, labeled from $$$l$$$ to $$$r$$$, with all vertices having $$$b_i \lt 0$$$ on the left and those with $$$b_i \gt 0$$$ on right. For each $$$i, j$$$ such that $$$l \le i, j \le r$$$, $$$b_i<0$$$ and $$$b_j>0$$$, draw an edge from $$$i$$$ to $$$j$$$ with infinite capacity and cost of unit flow as $$$|a_i-a_j|$$$.

 Add two more vertices: source $$$S$$$ and sink $$$T$$$.

 For each $$$i$$$ such that $$$l \le i \le r$$$ and $$$b_i<0$$$, add an edge from $$$S$$$ to $$$i$$$ with cost $$$0$$$ and capacity $$$|b_i|$$$.

 For each $$$i$$$ such that $$$l \le i \le r$$$ and $$$b_i>0$$$, add an edge from $$$i$$$ to $$$T$$$ with cost $$$0$$$ and capacity $$$|b_i|$$$.

 The cost of the subarray is then defined as the minimum cost of maximum flow from $$$S$$$ to $$$T$$$.

You are given $$$q$$$ queries in the form of two integers $$$l$$$ and $$$r$$$. You have to compute the cost of subarray $$$a[l:r]$$$ for each query, modulo $$$10^9 + 7$$$.

If you don't know what the minimum cost of maximum flow means, read here.

Input

The first line of input contains two integers $$$n$$$ and $$$q$$$ $$$(2 \leq n \leq 2\cdot 10^5, 1 \leq q \leq 2\cdot10^5)$$$  — length of arrays $$$a$$$, $$$b$$$ and the number of queries.

The next line contains $$$n$$$ integers $$$a_1,a_2 \ldots a_n$$$ ($$$0 \leq a_1 \le a_2 \ldots \le a_n \leq 10^9)$$$  — the array $$$a$$$. It is guaranteed that $$$a$$$ is sorted in non-decreasing order.

The next line contains $$$n$$$ integers $$$b_1,b_2 \ldots b_n$$$ $$$(-10^9\leq b_i \leq 10^9, b_i \neq 0)$$$  — the array $$$b$$$.

The $$$i$$$-th of the next $$$q$$$ lines contains two integers $$$l_i,r_i$$$ $$$(1\leq l_i \leq r_i \leq n)$$$. It is guaranteed that $$$ \sum\limits_{j = l_i}^{r_i} b_j = 0$$$.

Output

For each query $$$l_i$$$, $$$r_i$$$  — print the cost of subarray $$$a[l_i:r_i]$$$ modulo $$$10^9 + 7$$$.

Example

Input

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

Output

2
0
9
15

Note

In the first query, the maximum possible flow is $$$1$$$ i.e one unit from source to $$$2$$$, then one unit from $$$2$$$ to $$$3$$$, then one unit from $$$3$$$ to sink. The cost of the flow is $$$0 \cdot 1 + |2 - 4| \cdot 1 + 0 \cdot 1 = 2$$$.

In the second query, the maximum possible flow is again $$$1$$$ i.e from source to $$$7$$$, $$$7$$$ to $$$6$$$, and $$$6$$$ to sink with a cost of $$$0 \cdot |10 - 10| \cdot 1 + 0 \cdot 1 = 0$$$.

In the third query, the flow network is shown on the left with capacity written over the edge and the cost written in bracket. The image on the right shows the flow through each edge in an optimal configuration.
   Maximum flow is $$$3$$$ with a cost of $$$0 \cdot 3 + 1 \cdot 1 + 4 \cdot 2 + 0 \cdot 1 + 0 \cdot 2 = 9$$$.
In the fourth query, the flow network looks as –

The minimum cost maximum flow is achieved in the configuration –

The maximum flow in the above network is 4 and the minimum cost of such flow is 15.

question:
You are given two integer arrays $$$a$$$ and $$$b$$$ ($$$b_i \neq 0$$$ and $$$|b_i| \leq 10^9$$$). Array $$$a$$$ is sorted in non-decreasing order.
The cost of a subarray $$$a[l:r]$$$ is defined as follows:
- If $$$ \sum\limits_{j = l}^{r} b_j \neq 0$$$, then the cost is not defined.- Otherwise: Construct a bipartite flow graph with $$$r-l+1$$$ vertices, labeled from $$$l$$$ to $$$r$$$, with all vertices having $$$b_i \lt 0$$$ on the left and those with $$$b_i \gt 0$$$ on right. For each $$$i, j$$$ such that $$$l \le i, j \le r$$$, $$$b_i<0$$$ and $$$b_j>0$$$, draw an edge from $$$i$$$ to $$$j$$$ with infinite capacity and cost of unit flow as $$$|a_i-a_j|$$$. Add two more vertices: source $$$S$$$ and sink $$$T$$$. For each $$$i$$$ such that $$$l \le i \le r$$$ and $$$b_i<0$$$, add an edge from $$$S$$$ to $$$i$$$ with cost $$$0$$$ and capacity $$$|b_i|$$$. For each $$$i$$$ such that $$$l \le i \le r$$$ and $$$b_i>0$$$, add an edge from $$$i$$$ to $$$T$$$ with cost $$$0$$$ and capacity $$$|b_i|$$$. The cost of the subarray is then defined as the minimum cost of maximum flow from $$$S$$$ to $$$T$$$.You are given $$$q$$$ queries in the form of two integers $$$l$$$ and $$$r$$$. You have to compute the cost of subarray $$$a[l:r]$$$ for each query, modulo $$$10^9 + 7$$$.
If you don't know what the minimum cost of maximum flow means, read here.

Input
The first line of input contains two integers $$$n$$$ and $$$q$$$ $$$(2 \leq n \leq 2\cdot 10^5, 1 \leq q \leq 2\cdot10^5)$$$  — length of arrays $$$a$$$, $$$b$$$ and the number of queries.
The next line contains $$$n$$$ integers $$$a_1,a_2 \ldots a_n$$$ ($$$0 \leq a_1 \le a_2 \ldots \le a_n \leq 10^9)$$$  — the array $$$a$$$. It is guaranteed that $$$a$$$ is sorted in non-decreasing order.
The next line contains $$$n$$$ integers $$$b_1,b_2 \ldots b_n$$$ $$$(-10^9\leq b_i \leq 10^9, b_i \neq 0)$$$  — the array $$$b$$$.
The $$$i$$$-th of the next $$$q$$$ lines contains two integers $$$l_i,r_i$$$ $$$(1\leq l_i \leq r_i \leq n)$$$. It is guaranteed that $$$ \sum\limits_{j = l_i}^{r_i} b_j = 0$$$.

Output
For each query $$$l_i$$$, $$$r_i$$$  — print the cost of subarray $$$a[l_i:r_i]$$$ modulo $$$10^9 + 7$$$.

Example
Input
8 4
1 2 4 5 9 10 10 13
6 -1 1 -3 2 1 -1 1
2 3
6 7
3 5
2 6

Output
2
0
9
15

Note
In the first query, the maximum possible flow is $$$1$$$ i.e one unit from source to $$$2$$$, then one unit from $$$2$$$ to $$$3$$$, then one unit from $$$3$$$ to sink. The cost of the flow is $$$0 \cdot 1 + |2 - 4| \cdot 1 + 0 \cdot 1 = 2$$$.
In the second query, the maximum possible flow is again $$$1$$$ i.e from source to $$$7$$$, $$$7$$$ to $$$6$$$, and $$$6$$$ to sink with a cost of $$$0 \cdot |10 - 10| \cdot 1 + 0 \cdot 1 = 0$$$.
In the third query, the flow network is shown on the left with capacity written over the edge and the cost written in bracket. The image on the right shows the flow through each edge in an optimal configuration.
 ![image](1.png)  Maximum flow is $$$3$$$ with a cost of $$$0 \cdot 3 + 1 \cdot 1 + 4 \cdot 2 + 0 \cdot 1 + 0 \cdot 2 = 9$$$.In the fourth query, the flow network looks as –
 ![image](2.png) The minimum cost maximum flow is achieved in the configuration –
 ![image](3.png) The maximum flow in the above network is 4 and the minimum cost of such flow is 15.

image_tags: Graph Graph Graph

data_split: test


raw_problem:
A square is drawn around a circle as shown in the diagram below on the left.

We shall call the blue shaded region the L-section.

A line is drawn from the bottom left of the square to the top right as shown in the diagram on the right.

We shall call the orange shaded region a <dfn>concave triangle</dfn>.

It should be clear that the concave triangle occupies exactly half of the L-section.

Two circles are placed next to each other horizontally, a rectangle is drawn around both circles, and a line is drawn from the bottom left to the top right as shown in the diagram below.

This time the concave triangle occupies approximately 36.46% of the L-section.

If $n$ circles are placed next to each other horizontally, a rectangle is drawn around the <var>n</var> circles, and a line is drawn from the bottom left to the top right, then it can be shown that the least value of <var>n</var> for which the concave triangle occupies less than 10% of the L-section is $n = 15$.

What is the least value of $n$ for which the concave triangle occupies less than 0.1% of the L-section?

problem:
A square is drawn around a circle as shown in the diagram below on the left.
We shall call the blue shaded region the L-section.
A line is drawn from the bottom left of the square to the top right as shown in the diagram on the right.
We shall call the orange shaded region a concave triangle.

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

It should be clear that the concave triangle occupies exactly half of the L-section.

Two circles are placed next to each other horizontally, a rectangle is drawn around both circles, and a line is drawn from the bottom left to the top right as shown in the diagram below.

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

This time the concave triangle occupies approximately 36.46% of the L-section.

If $n$ circles are placed next to each other horizontally, a rectangle is drawn around the n circles, and a line is drawn from the bottom left to the top right, then it can be shown that the least value of n for which the concave triangle occupies less than 10% of the L-section is $n = 15$.

What is the least value of $n$ for which the concave triangle occupies less than 0.1% of the L-section?

solutions: "import itertools, math\n\n\n# Start by defining the coordinate system in a convenient way. The position and scale of the diagram don't\n# matter because we only care about the ratio of areas, not the absolute areas. So, let the bottom left\n# of the diagram be the origin (x = 0, y = 0), and let each circle to have a radius of 1.\n# \n# The leftmost circle is centered at (1, 1), and its equation is (x - 1)^2 + (y - 1)^2 = 1.\n# The diagonal line has slope = s = 1 / n (for any positive n), and the line's equation is y = s * x.\n# From basic geometry, the area of the blue L-section is 1 - pi / 4.\n# \n# Let's find the x-coordinate where the diagonal line intersects the first circle.\n# Take the equation of the circle and substitute y = s * x for the line:\n# \n#   (x - 1)^2 + (s*x - 1)^2 = 1.\n#   (x^2 - 2x + 1) + (s^2 x^2 - 2s*x + 1) = 1.\n#   (1 + s^2)x^2 + (-2 - 2s)x + 1 = 0.\n# \n# We can apply the quadratic formula with a = 1 + s^2, b = -2 - 2s, c = 1. There are two solutions for x,\n# and we only want the smaller value. Thus, let X = (-b - sqrt(b^2 - 4ac)) / (2a). Or equivalently\n# with more numerical stability (using the Citardauq formula), X = (2c) / (-b + sqrt(b^2 - 4ac)).\n# \n# The orange concave triangle can be divided into two parts by a vertical line:\n# \n# - The left part is a proper triangle, whose area is easily seen as x * y / 2 = X^2 * s / 2.\n# \n# - The right part is the region between the circle and the baseline. Let's re-express\n#   the circle's equation in terms of y, and only keep the lower semicircle:\n#   \n#     (x - 1)^2 + (y - 1)^2 = 1.\n#     (y - 1)^2 = 1 - (x - 1)^2.\n#     y - 1 = -sqrt(1 - (x - 1)^2).\n#     y = 1 - sqrt(1 - (x - 1)^2).\n#     y = 1 - sqrt(1 - (x^2 - 2x + 1)).\n#     y = 1 - sqrt(2x - x^2).\n#   \n#   Now, the indefinite integral of f(x) = 1 - sqrt(2x - x^2) with respect to x\n#   is F(x) = (x - 1) - [sqrt(2x - x^2) * (x - 1) + asin(x - 1)] / 2.\n#   Finding this integral is not obvious, but verifying it is a fairly straightforward\n#   mechanical procedure involving differentiation and simplification.\n#   \n#   The area of the right part is the integral of f(x) for x from X to 1, because the start is\n#   the x-coordinate where line meets the circle, and the end is where the circle meets the baseline.\n#   Hence the area is equal to F(1) - F(X).\n# \n# All in all, for any given n, the area of the orange concave triangle is X^2 * s / 2 + F(1) - F(X).\n# The rest of the algorithm is a brute-force search with n = 1, 2, 3, ... until the ratio condition is met.\n# \n# Additional notes:\n# - Intuitively, as n increases and the slope gets smaller, the area of the orange concave triangle should strictly\n#   decrease. This statement is in fact true, but proving it involves a big pile of differentiation and algebra.\n#   0. We need to show that X (which is the x-coordinate of the line-circle intersection) increases with n.\n#      We'd differentiate X with respect to n, and get an expression that is always positive for any positive n.\n#   1. Because X increases with n, the area of the right part, with its always-positive integrand, must decrease.\n#   2. As for the left part, we'd differentiate X^2 * s / 2 with respect to n, and get a huge messy formula.\n#      It turns out this formula is negative for all n > 1. Hence the area of this triangle also decreases with n.\n#   After we prove that increasing n leads to decreasing orange area, we could use\n#   binary search to find the minimum value of n needed to meet the ratio requirement.\n# - The use of floating-point arithmetic, for basic arithmetic operations (+ - * /) and irrational functions (sqrt,\n#   asin) alike, is inherently difficult or impossible to prove the correctness of. Furthermore, the algorithms\n#   for irrational functions are hard to understand and beyond the scope of this problem, and the error bounds for\n#   all operations are difficult to reason about.\n#   It should be possible to solve this particular problem using only integer arithmetic in a provably correct way.\n#   The basic idea would be to round the result of each operation both down and up to an integer fraction,\n#   keep track of pessimistic intervals that are guaranteed to contain the true value, accept a comparison only\n#   if the intervals don't overlap, and recompute everything at a higher precision if a comparison is inconclusive.\n#   Note: Because it doesn't seem easy to compute pi and asin(), it might be better to\n#   approximate integrals directly using the Darboux definition of lower and upper sums.\ndef compute():\n\t# The indefinite integral of (1 - sqrt(2x - x^2)) dx.\n\tdef integral(x):\n\t\tt = x - 1.0\n\t\treturn t - (math.sqrt(x * (2.0 - x)) * t + math.asin(t)) / 2.0\n\t\n\tlsectionarea = 1.0 - math.pi / 4.0\n\tfor i in itertools.count(1):\n\t\tslope = 1.0 / i\n\t\ta = slope**2 + 1.0\n\t\tb = -2.0 * (slope + 1.0)\n\t\tc = 1.0\n\t\tx = (2.0 * c) / (-b + math.sqrt(b * b - 4 * a * c))\n\t\tconcavetrianglearea = (x**2 * slope / 2) + (integral(1.0) - integral(x))\n\t\tif concavetrianglearea / lsectionarea < 0.001:\n\t\t\treturn str(i)\n\n\nprint(compute())\n"

question:
A square is drawn around a circle as shown in the diagram below on the left.
We shall call the blue shaded region the L-section.
A line is drawn from the bottom left of the square to the top right as shown in the diagram on the right.
We shall call the orange shaded region a concave triangle.

![image](1.png)

It should be clear that the concave triangle occupies exactly half of the L-section.

Two circles are placed next to each other horizontally, a rectangle is drawn around both circles, and a line is drawn from the bottom left to the top right as shown in the diagram below.

![image](2.png)

This time the concave triangle occupies approximately 36.46% of the L-section.

If $n$ circles are placed next to each other horizontally, a rectangle is drawn around the $n$ circles, and a line is drawn from the bottom left to the top right, then it can be shown that the least value of $n$ for which the concave triangle occupies less than 10% of the L-section is $n = 15$.

What is the least value of $n$ for which the concave triangle occupies less than 0.1% of the L-section?

image_tags:
2D Geometry
2D Geometry

data_split: test

source: project euler


F. Ehab and a weird weight formula

problem_index: F

time_limit: 2.5 seconds

memory_limit: 256 megabytes

note:
In the first sample, the tree itself minimizes the value of $$$w$$$.
In the second sample, the optimal tree is:
![image](images/cf_1088_F/1.png)

source: codeforces

raw_problem:
F. Ehab and a weird weight formula

time limit per test
2.5 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

You're given a tree consisting of $$$n$$$ nodes. Every node $$$u$$$ has a weight $$$a_u$$$. It is guaranteed that there is only one node with minimum weight in the tree. For every node $$$u$$$ (except for the node with the minimum weight), it must have a neighbor $$$v$$$ such that $$$a_v<a_u$$$. You should construct a tree to minimize the weight $$$w$$$ calculated as follows:

 For every node $$$u$$$, $$$deg_u \cdot a_u$$$ is added to $$$w$$$ ($$$deg_u$$$ is the number of edges containing node $$$u$$$).

 For every edge $$$\{ u,v \}$$$, $$$\lceil log_2(dist(u,v)) \rceil \cdot min(a_u,a_v)$$$ is added to $$$w$$$, where $$$dist(u,v)$$$ is the number of edges in the path from $$$u$$$ to $$$v$$$ in the given tree.

Input

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

The second line contains $$$n$$$ space-separated integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$, the weights of the nodes.

The next $$$n-1$$$ lines, each contains 2 space-separated integers $$$u$$$ and $$$v$$$ $$$(1 \le u,v \le n)$$$ which means there's an edge between $$$u$$$ and $$$v$$$.

Output

Output one integer, the minimum possible value for $$$w$$$.

Examples

Input

3
1 2 3
1 2
1 3

Output

7

Input

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

Output

40

Note

In the first sample, the tree itself minimizes the value of $$$w$$$.

In the second sample, the optimal tree is:

question:
You're given a tree consisting of $$$n$$$ nodes. Every node $$$u$$$ has a weight $$$a_u$$$. It is guaranteed that there is only one node with minimum weight in the tree. For every node $$$u$$$ (except for the node with the minimum weight), it must have a neighbor $$$v$$$ such that $$$a_v<a_u$$$. You should construct a tree to minimize the weight $$$w$$$ calculated as follows:
 -  For every node $$$u$$$, $$$deg_u \cdot a_u$$$ is added to $$$w$$$ ($$$deg_u$$$ is the number of edges containing node $$$u$$$). -  For every edge $$$\{ u,v \}$$$, $$$\lceil log_2(dist(u,v)) \rceil \cdot min(a_u,a_v)$$$ is added to $$$w$$$, where $$$dist(u,v)$$$ is the number of edges in the path from $$$u$$$ to $$$v$$$ in the given tree.
Input
The first line contains the integer $$$n$$$ $$$(2 \le n \le 5 \cdot 10^5)$$$, the number of nodes in the tree.
The second line contains $$$n$$$ space-separated integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$, the weights of the nodes.
The next $$$n-1$$$ lines, each contains 2 space-separated integers $$$u$$$ and $$$v$$$ $$$(1 \le u,v \le n)$$$ which means there's an edge between $$$u$$$ and $$$v$$$.

Output
Output one integer, the minimum possible value for $$$w$$$.

Examples
Input
3
1 2 3
1 2
1 3

Output
7

Input
5
4 5 3 7 8
1 2
1 3
3 4
4 5

Output
40

Note
In the first sample, the tree itself minimizes the value of $$$w$$$.
In the second sample, the optimal tree is:
![image](1.png)

skill_types: ['Data structures']

data_split: test


E. Playing with String

problem_index: E

time_limit: 2 seconds

memory_limit: 256 megabytes

solutions: ["U = input()\nmemo = {}\nDP = [0] * (len(U) + 1)\nDP[0] = 0\nfor j in range(1, len(U) + 1):\n\ts = set()\n\tfor i in range(j):\n\t\ts.add(DP[max(0, i - 1)] ^ DP[max(0, j - i - 2)])\n\tmex = 0\n\twhile mex in s:\n\t\tmex += 1\n\tDP[j] = mex\nmemo2 = {}\n\ndef Grundy(S):\n\tif S in memo2:\n\t\treturn memo2[S]\n\ttotal = 0\n\tconsec = 0\n\tfor i in range(1, len(S) - 1):\n\t\tif S[i - 1] == S[i + 1]:\n\t\t\tconsec += 1\n\t\telse:\n\t\t\ttotal ^= DP[consec]\n\t\t\tconsec = 0\n\ttotal ^= DP[consec]\n\tmemo2[S] = total\n\treturn total\nimport sys\nsys.setrecursionlimit(3000)\nif Grundy(U) != 0:\n\tfor i in range(1, len(U) - 1):\n\t\tif U[i - 1] == U[i + 1]:\n\t\t\tif Grundy(U[:i]) ^ Grundy(U[i + 1:]) == 0:\n\t\t\t\tprint('First')\n\t\t\t\tprint(i + 1)\n\t\t\t\tbreak\nelse:\n\tprint('Second')\n"]

difficulty: HARD

source: codeforces

sample_tests: {"inputs": ["abacaba", "abcde"], "outputs": ["First\n2", "Second"]}

raw_problem:
E. Playing with String

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Two people play the following string game. Initially the players have got some string s. The players move in turns, the player who cannot make a move loses.

Before the game began, the string is written on a piece of paper, one letter per cell.
  An example of the initial situation at s = "abacaba"
A player's move is the sequence of actions:

 The player chooses one of the available pieces of paper with some string written on it. Let's denote it is t. Note that initially, only one piece of paper is available.

 The player chooses in the string t = t1t2... t|t| character in position i (1 ≤ i ≤ |t|) such that for some positive integer l (0 < i - l; i + l ≤ |t|) the following equations hold: ti - 1 = ti + 1, ti - 2 = ti + 2, ..., ti - l = ti + l.

 Player cuts the cell with the chosen character. As a result of the operation, he gets three new pieces of paper, the first one will contain string t1t2... ti - 1, the second one will contain a string consisting of a single character ti, the third one contains string ti + 1ti + 2... t|t|.

  An example of making action (i = 4) with string s = «abacaba»
Your task is to determine the winner provided that both players play optimally well. If the first player wins, find the position of character that is optimal to cut in his first move. If there are multiple positions, print the minimal possible one.

Input

The first line contains string s (1 ≤ |s| ≤ 5000). It is guaranteed that string s only contains lowercase English letters.

Output

If the second player wins, print in the single line "Second" (without the quotes). Otherwise, print in the first line "First" (without the quotes), and in the second line print the minimal possible winning move — integer i (1 ≤ i ≤ |s|).

Examples

Input

abacaba

Output

First
2

Input

abcde

Output

Second

Note

In the first sample the first player has multiple winning moves. But the minimum one is to cut the character in position 2.

In the second sample the first player has no available moves.

question:
Two people play the following string game. Initially the players have got some string s. The players move in turns, the player who cannot make a move loses.
Before the game began, the string is written on a piece of paper, one letter per cell.
 ![image](1.png) An example of the initial situation at s = "abacaba" A player's move is the sequence of actions:
 -  The player chooses one of the available pieces of paper with some string written on it. Let's denote it is t. Note that initially, only one piece of paper is available. -  The player chooses in the string t = t_{1}t_{2}... t_{|t|} character in position i (1 ≤ i ≤ |t|) such that for some positive integer l (0 < i - l; i + l ≤ |t|) the following equations hold: t_{i - 1} = t_{i + 1}, t_{i - 2} = t_{i + 2}, ..., t_{i - l} = t_{i + l}. -  Player cuts the cell with the chosen character. As a result of the operation, he gets three new pieces of paper, the first one will contain string t_{1}t_{2}... t_{i - 1}, the second one will contain a string consisting of a single character t_{i}, the third one contains string t_{i + 1}t_{i + 2}... t_{|t|}.  ![image](2.png) An example of making action (i = 4) with string s = «abacaba» Your task is to determine the winner provided that both players play optimally well. If the first player wins, find the position of character that is optimal to cut in his first move. If there are multiple positions, print the minimal possible one.

Input
The first line contains string s (1 ≤ |s| ≤ 5000). It is guaranteed that string s only contains lowercase English letters.

Output
If the second player wins, print in the single line "Second" (without the quotes). Otherwise, print in the first line "First" (without the quotes), and in the second line print the minimal possible winning move — integer i (1 ≤ i ≤ |s|).

Examples
Input
abacaba

Output
First
2

Input
abcde

Output
Second

Note
In the first sample the first player has multiple winning moves. But the minimum one is to cut the character in position 2.
In the second sample the first player has no available moves.

image_tags:
Linear Data Structure
Linear Data Structure

data_split: test


Weather Forecaster

source: 14th Japanese Olympiad in Informatics, Preliminary Round

raw_problem:
気象予報士 (Weather Forecaster)

問題

JOI 市は南北方向に H キロメートル，東西方向に W キロメートルの長方形の形をしており，H × W 個の 1 キロメートル四方の小区画に区切られている．北から i 番目，西から j 番目の小区画を (i, j) と表す．

各小区画は上空に雲があるか雲がないかのどちらかである．すべての雲は，1 分経つごとに 1 キロメートル東に移動する．今日は実に天気が良いため，JOI 市の外から JOI 市内に雲が移動してくることはない．

今，各小区画の上空に雲があるかないかがわかっている．気象予報士であるあなたは，各小区画について，今から何分後に初めてその小区画の上空に雲が来るかを予測することになった．

各小区画について，今から何分後に初めてその小区画の上空に雲が来るか求めよ．

入力

入力は 1 + H 行からなる．

1 行目には，整数 H, W (1 ≤ H ≤ 100, 1 ≤ W ≤ 100) が空白を区切りとして書かれている．これは，JOI 市が H × W 個の 1 キロメートル四方の小区画に区切られていることを表す．

続く H 行のうちの i 行目 (1 ≤ i ≤ H) には W 文字からなる文字列が書かれている．W 文字のうちの j 文字目 (1 ≤ j ≤ W) は，小区画 (i, j) の上空に，今，雲があるかどうかを表す．雲がある場合は文字 'c' (英小文字) が，雲がない場合は文字 '.' (ピリオド) が書かれている．

出力

出力は H 行からなり，それぞれの行は空白を区切りとした W 個の整数からなる．出力の i 行目の j 番目の整数 (1 ≤ i ≤ H, 1 ≤ j ≤ W) は，今から何分後に初めて小区画 (i, j) の上空に雲が来るかを表さなければならない．ただし，今すでに小区画 (i, j) の上空に雲がある場合は 0 を，何分経っても小区画 (i, j) の上空に雲が来ない場合は -1 を出力せよ．

出力の各行の行頭と行末には余計な空白を入れないこと．

入出力例

入力例 1

3 4
c..c
..c.
....

出力例 1

0 1 2 0
-1 -1 0 1
-1 -1 -1 -1

入力例 2

6 8
.c......
........
.ccc..c.
....c...
..c.cc..
....c...

出力例 2

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

入出力例 1 では，JOI 市は 3 × 4 個の小区画に区切られている．今の JOI 市の雲の状況は以下の通りである．図の上が北を表す．

この後，1 分ごとに雲は以下のように移動する．

問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。

solutions: ["# AOJ 0610: Weather Forecaster\n# Python3 2018.7.2 bal4u\n\nimport sys\nfrom sys import stdin\ninput = stdin.readline\n\nh, w = map(int, input().split())\nans = [[0 for c in range(w)] for r in range(h)]\narr = [input().strip() for r in range(h)]\nfor r in range(h):\n\tp = -1\n\tfor c in range(w):\n\t\tif arr[r][c] == 'c': p = c\n\t\tans[r][c] = -1 if p < 0 else c-p\nfor r in range(h): print(*ans[r])\n", "H, W = map(int, input().split())\nfor i in range(H):\n    s = input()\n    cnt = -1\n    res = []\n    for j in range(W):\n        if s[j] == 'c':\n            cnt = 0\n        else:\n            if cnt != -1:\n                cnt += 1\n        res.append(cnt)\n    print(*res)\n", "h, w = map(int, input().split())\nans = []\nfor _ in range(h):\n  s = input()\n  lst = []\n  acc = -1\n  for c in s:\n    if c == \"c\":\n      acc = 0\n    elif acc == -1:\n      pass\n    else:\n      acc += 1\n    lst.append(acc)\n  ans.append(lst)\nfor lst in ans:\n  print(*lst)\n", "import sys\n\n# READ_FROM_FILE = True\nREAD_FROM_FILE = False\n\n\ndef main():\n    if READ_FROM_FILE:\n        f = open('test0.txt', 'r')\n    else:\n        f = sys.stdin\n\n    height, width = map(int, f.readline().split())\n    for _ in range(height):\n        i_str = f.readline().rstrip('\\n')\n        result_list = []\n        c_idx = -1\n        for x in range(width):\n            if i_str[x] == 'c':\n                result_list.append(0)\n                c_idx = x\n            elif c_idx < 0:\n                result_list.append(-1)\n            else:\n                result_list.append(x - c_idx)\n        print(*result_list)\n\n    if READ_FROM_FILE:\n        f.close()\n    return\n\n\nif __name__ == '__main__':\n    main()\n\n", "h,w=map(int,input().split())\nwhile h:\n    h-=1\n    n=input()\n    c=-1\n    for i in range(w-1):\n        if n[i]=='c':c=0\n        print(c,end=\" \")\n        if c!=-1:c+=1\n        if n[i+1]=='c':c=0\n    print(c)\n", "h,w=list(map(int,input().split()))\ns=[input().rstrip() for i in range(h)]\nans=[[-1 for i in range(w)] for i in range(h)]\nfor i in range(h):\n  c=-1\n  for j in range(w):\n    if s[i][j]=='c':\n      c=j\n    if c!=-1:\n      ans[i][j]=j-c\nprint('\\n'.join(map(lambda x: ' '.join(map(str,x)),ans)))\n", "# \u6c17\u8c61\u4e88\u5831\u58eb (Weather Forecaster)\n\n\ndef main():\n\n    H,W = map(int, input().split())\n    towns = [list(input().strip()) for _ in range(H)]\n    ans = [[-1]*W for _ in range(H)]\n    for h in range(H):\n        if towns[h][0] == 'c':\n            ans[h][0] = 0\n    \n    for h in range(H):\n        for w in range(1,W):\n            if towns[h][w] == 'c':\n                ans[h][w] = 0\n            elif ans[h][w-1] != -1:\n                ans[h][w] = ans[h][w-1] + 1\n    \n    for h in range(H):\n        print(*ans[h])\n\nif __name__ == '__main__':\n    main()\n\n", "H,W=[int(i) for i in input().split(\" \")]\n\ncity=[]\nfor i in range(H):\n    C=input()\n    row=[]\n    timer=-1000\n    for c in C:\n        if c==\"c\":\n            timer=0\n            row.append(timer)\n        else:\n            timer+=1\n            row.append(timer)\n    city.append(row)\n\n\nfor i in range(H):\n    for j in range(W):\n        if city[i][j]<0:\n            city[i][j]=\"-1\"\n        else:\n            city[i][j]=str(city[i][j])\n\nfor c in city:\n    print(\" \".join(c))\n\n", "n,m=map(int,input().split())\ntown=[]\nfor i in range(n):\n    weather=input()\n    c=-1\n    t_c=[]\n    for j in range(m):\n        if weather[j]==\"c\":c=0\n        t_c.append(c)\n        if c>-1:c+=1\n    town.append(t_c)\nfor i in town:print(' '.join(map(str,i)))\n", "h, w = map(int, input().split())\n\nfor _ in range(h):\n    cloud = list(input())\n    cnt = -1\n    flag = False\n    ans = []\n    for c in cloud:\n        if c == \"c\":\n            flag = True\n            cnt = 0\n        elif flag:\n            cnt += 1\n        ans.append(cnt)\n    print(' '. join(str(a) for a in ans))\n", "H, W = map(int, input().split())\nC = list(str(input()) for x in range(H))\nA = list(list(-1 for x in range(W)) for y in range(H))\n\nck = 0\nfor i in range(H):\n    for j in range(W):\n        if C[i][j] == \"c\":\n            A[i][j] = 0\n            ck += 1\n            for k in range(j+1, W):\n                A[i][k] = ck\n                ck += 1\n            ck = 0\n\nfor i in range(H):\n    print(*A[i])\n", "h, w = map(int, input().split())\ns = []\nfor _ in range(h):\n    s.append(input())\nc = [[0 for i in range(w)] for j in range(h)]\nfor i in range(h):\n    p = -1\n    for j in range(w):\n        if s[i][j] == \".\":\n            if p == -1:\n                c[i][j] = -1\n            else:\n                p += 1\n                c[i][j] = p\n        else:\n            p = 0\n            c[i][j] = p\nfor i in c:\n    print(\" \".join(map(str, i)))\n", "h, w = map(int, input().split())\ncloud = [input() for _ in range(h)]\n\nans = [[-1] * w for _ in range(h)]\n\nfor i in range(h):\n    for j in range(w):\n        if cloud[i][j] == \"c\":\n            ans[i][j] = 0\n        elif j > 0 and ans[i][j - 1] >= 0:\n            ans[i][j] = ans[i][j - 1] + 1\n\nfor ans_i in ans:\n    print(*ans_i)\n\n", "H,W =map(int,input().split())\ngrid = [list(input()) for _ in range(H)]\n\nans = [[-1]*W for _ in range(H)]\nfor h in range(H):\n    d = -1\n    for w in range(W):\n        if grid[h][w] == 'c':\n            d = 0\n        elif d != -1:\n            d += 1\n        ans[h][w] = d\n\nfor h in range(H):\n    print(*ans[h])\n", "H, W = map(int, input().split(\" \"))\n\nfor _ in range(H):\n\tC = input()\n\tpre = 0\n\tresult = []\n\tfor i in range(W):\n\t\tif C[i] == \"c\":\n\t\t\tresult.append(0)\n\t\t\tpre = 1\n\t\telif pre > 0:\n\t\t\tresult.append(pre)\n\t\t\tpre += 1\n\t\telse:\n\t\t\tresult.append(-1)\n\ts = list(map(str, result))\n\tprint(\" \".join(s))\n", "h,w = map(int, input().split())\nfor _ in range(h):\n    s = input()\n    ans = []\n    for i in range(len(s)):\n        if s[i] == 'c':\n            ans.append(0)\n        elif i == 0:\n            ans.append(-1)\n        else:\n            for j in range(1,i+1):\n                if s[i-j] == 'c':\n                    ans.append(j)\n                    break\n                if j == i:\n                    ans.append(-1)\n    print(' '.join(map(str, ans)))\n\n", "h, w = map(int, input().split())\nfor _ in range(h):\n    a = input()\n    ans = [0] * w\n    t = -1\n    for i in range(w):\n        if a[i] == \"c\":\n            t = 0\n            ans[i] = 0\n        else:\n            if t == -1:\n                ans[i] = -1\n            else:\n                t += 1\n                ans[i] = t\n    print(*ans)\n    \n", "h,w = map(int,input().split())\nans = [[0] * w for i in range(h)]\nc_m = []\nfor i in range(h):\n    c_lis = input()\n    c_m.append(list(c_lis))\nfor j in range(h):\n    for k in range(w):\n        if ans[j][k] == 0 and c_m[j][k] == '.':\n            ans[j][k] = -1\n        elif c_m[j][k] == 'c':\n            for l in range(w - k):\n                ans[j][k + l] = l\nfor m in range(h):\n    cha = str(ans[m][0])\n    for n in range(w -1):\n        cha = cha + \" \" + str(ans[m][n + 1])\n    print(cha)\n", "h,w=[int(s)for s in input().split(\" \")]\nmap_=[[True if c=='c' else False for c in input()]for i in range(h)]\ndis=[['' for i in range(w)]for j in range(h)]\nfor i in range(h):\n    distance=-1\n    for j in range(w):\n        if map_[i][j]==True:distance=0\n        elif distance!=-1:distance+=1\n        dis[i][j]=str(distance)\nfor d in dis:\n    print(' '.join(d))\n", "H, W = map(int, input().split())\nA = []\nfor _ in range(H): A.append((input().strip()))\nfor h in range(H):\n\tfor w in range(W):\n\t\tif A[h][w]=='c':\n\t\t\ttmp = 0\n\t\telif A[h][0:w].count('c')==0:\n\t\t\ttmp = -1\n\t\telse:\n\t\t\ttmp = w-A[h][0:w].rindex('c')\n\t\tif w == W-1:\n\t\t\tprint(tmp)\n\t\telse:\n\t\t\tprint(tmp, end=' ')\n\n", "H, W = map(int, input().split())\n\nC = [input() for i in range(H)]\nA = [[0 for j in range(W)] for i in range(H)]\n\nfor i in range(H):\n    for j in range(W):\n        d = 0\n        for k in range(j, -1, -1):\n            if C[i][k] == 'c':\n                break\n            d += 1\n        else:\n            d = -1\n\n        A[i][j] = d\n\nfor i in range(H):\n    print(' '.join(map(str, A[i])))\n\n\n\n\n", "h,w=map(int,input().split())\nc=[list(input()) for _ in range(h)]\nans=[[0]*w for _ in range(h)]\nfor i in range(h):\n    for j in range(w):\n        if c[i][j]=='.':\n            if c[i][:j].count('c')==0:\n                ans[i][j]=-1\n            else:\n                for k in range(1,j+1):\n                    if c[i][j-k]=='c':\n                        ans[i][j]=k\n                        break\nfor i in ans:\n    print(*i)\n", "#C\u554f\u984c\nH,W = map(int,input().split())\nG = [list(str(input())) for i in range(H)]\nans = [[0 for i in range(W)] for j in range(H)]\n\nfor i in range(H):\n    g = G[i]\n    cnow = -1\n    for j in range(W):\n        if g[j] == \"c\":\n            cnow = j\n            ans[i][j] = 0\n        else:\n            if cnow == -1:\n                ans[i][j] = -1\n            else:\n                ans[i][j] = j-cnow\n                \nfor a in ans:\n    print(*a)\n\n\n", "# coding: utf-8\n\nH, W = list(map(int, input().split(' ')))\nsections = [list(input()) for i in range(H)]\n\ncrowds = [[-1 for w in range(W)] for h in range(H)]\n\nfor h in range(H):\n    c = -1\n    for w in range(W):\n        if c >= 0: c += 1\n        if sections[h][w] == 'c': c = 0\n        crowds[h][w] = c\n\nfor row in crowds:\n    print(' '.join(list(map(str, row))))\n", "H, W = map(int, input().split())\nfor i in range(H):\n    s = input()\n    cnt = -1\n    res = []\n    for j in range(W):\n        if s[j] == 'c':\n            cnt = 0\n        else:\n            if cnt != -1:\n                cnt += 1\n        res.append(cnt)\n    print(*res)\n\n", "h, w = map(int, input().split())\nans = []\nfor _ in range(h):\n    data = [i for i in input()]\n    cnt = 1\n    for i in range(w-1):\n        if (data[i] == \"c\" and data[i+1] == \".\") or (type(data[i]) == int and data[i+1] == \".\"):\n            data[i+1] = cnt\n            cnt += 1\n        else:\n            cnt = 1\n\n    data = [\"-1\" if d == \".\" else d for d in data]\n    data = [\"0\" if d == \"c\" else d for d in data]\n    data = list(map(str, data))\n    print(*data)\n", "# coding: utf-8\nh, w = map(int, input().split())\ncloud = [[i for i in input()] for i in range(h)]\nflag = 0 #1?????\u00a8????????????\ncnt = 0 \nfor i in range(h):\n    for j in range(w):\n        if j==w-1 and flag==0 and cloud[i][j]=='.':\n            print(-1, end='')\n        elif j==w-1 and cloud[i][j]=='c':\n            print(0, end='')\n            flag = 1\n            cnt = 0\n        elif j==w-1 and cloud[i][j]=='.':\n            cnt += 1\n            print(cnt, end='')\n        elif flag==0 and cloud[i][j]=='.':\n            print(-1, end=' ')\n        elif cloud[i][j]=='c':\n            print(0, end=' ')\n            flag = 1\n            cnt = 0\n        else:\n            cnt += 1\n            print(cnt, end=' ')\n    print()\n    cnt = 0\n    flag = 0\n", "h, w = map(int, input().split())    # \u533a\u753b\u306e\u5927\u304d\u3055\u306e\u53d7\u3051\u53d6\u308a\n\nl = [list(input()) for _ in range(h)]   # \u5c0f\u533a\u753b\u306e\u96f2\u306e\u6709\u7121\u306e\u53d7\u3051\u53d6\u308a\n\nans = [[-1]*w for _ in range(h)]    # \u4f55\u5206\u5f8c\u306b\u96f2\u304c\u6765\u308b\u304b\u306e\u30ea\u30b9\u30c8\u3067\uff0c\u5404\u5c0f\u533a\u753b\u3092-1\u3067\u521d\u671f\u5316\n\nfor i in range(h):  # \u5357\u5317\u65b9\u5411\u306b\u3064\u3044\u3066\n    for j in range(w):  # \u6771\u897f\u65b9\u5411\u306b\u3064\u3044\u3066\n        if l[i][j] == 'c':  # \u5c0f\u533a\u753b\u306b\u96f2\u304c\u3042\u308c\u3070\n            k = j   # k\u306b\u79fb\u52d5\u3059\u308b\u3068\u304d\n            while k < w:    # \u6771\u304b\u3089\u5e02\u5916\u306b\u306f\u307f\u51fa\u3059\u307e\u3067\n                ans[i][k] = k-j # k\u306b\u306fk-j\u5206\u5f8c\u306b\u96f2\u304c\u6765\u308b\n                k += 1  # k\u30921\u5897\u3084\u3059\n\nfor i in range(h):  # \u5357\u5317\u65b9\u5411\u306b\u3064\u3044\u3066\n    for j in range(w):  # \u6771\u897f\u65b9\u5411\u306b\u3064\u3044\u3066\n        print(ans[i][j], end= ' ' if j+1!=w else '\\n')  # \u4f55\u5206\u5f8c\u306b\u96f2\u304c\u6765\u308b\u304b\u3092\u51fa\u529b\n"]

source: aizu

question:
Weather Forecaster
Problem

JOI City is in the shape of a rectangle extending H kilometers North-to-South and W kilometers East-to-West, and is divided into H × W squares, each one kilometer on a side. The square in the i-th position from the North and the j-th from the West is expressed as (i, j).

Each square either has clouds above it or does not. All clouds move one kilometer to the East every minute. Today, the weather is quite nice, hence clouds will not move from outside into JOI City.

Currently, it is known whether there are clouds above each square. As a weather forecaster, you have been tasked to predict how many minutes from now it will be before clouds come over each square for the first time.

Find out how many minutes from now it will be before clouds come over each square for the first time.

Input

The input consists of 1 + H lines.

The first line contains the integers H, W (1 ≤ H ≤ 100, 1 ≤ W ≤ 100), separated by a space. This indicates that JOI City is divided into H × W squares, each one kilometer on a side.

For each of the following H lines, the i-th line (1 ≤ i ≤ H) contains a string of W characters. The j-th character (1 ≤ j ≤ W) of the W characters indicates whether there are clouds above the square (i, j) right now. If there are clouds, the character 'c' (lower case letter) is written; if there are no clouds, the character '.' (period) is written.

Output

The output consists of H lines, each made up of W integers separated by a space. The j-th integer on the i-th line of the output (1 ≤ i ≤ H, 1 ≤ j ≤ W) must represent how many minutes from now it will be before clouds come over the square (i, j) for the first time. However, if there are already clouds above the square (i, j), output 0, and if clouds will never come over the square (i, j), output -1.

Do not include extra spaces at the beginning or end of each line in the output.

Example Input and Output
Input Example 1

3 4
c..c
..c.
....

Output Example 1

0 1 2 0
-1 -1 0 1
-1 -1 -1 -1

Input Example 2

6 8
.c......
........
.ccc..c.
....c...
..c.cc..
....c...

Output Example 2

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

In Example Input 1, JOI City is divided into 3 × 4 squares. The current cloud situation in JOI City is as follows. The top of the diagram represents North.

![image](1.png)

Afterward, every minute, clouds will move as follows:

![image](2.png)
![image](3.png)
![image](4.png)

The problem statement and the data used for automatic judging are created and made public by the Japanese Committee for the International Olympiad in Informatics.

image_tags: Map Map Map Map

data_split: test


C. Maxim and Matrix

problem_index: C

time_limit: 2 seconds

memory_limit: 256 megabytes

solutions: ["(n, t) = map(int, input().split())\ns = bin(n + 2)[2:]\nl = len(s)\nif t & t - 1:\n\tans = 0\nelse:\n\tt = t.bit_length()\n\tf = [[0] * (l + 1) for i in range(l + 1)]\n\tfor i in range(l + 1):\n\t\tf[i][0] = f[i][i] = 1\n\t\tfor j in range(1, i):\n\t\t\tf[i][j] = f[i - 1][j - 1] + f[i - 1][j]\n\tans = c = 0\n\tfor i in range(l):\n\t\tif s[i] == '1':\n\t\t\tif t - c <= l - i - 1:\n\t\t\t\tans += f[l - i - 1][t - c]\n\t\t\tc += 1\n\tif t == 1:\n\t\tans -= 1\nprint(ans)\n", "from math import factorial as fac\n(n, t) = map(int, input().split())\nif t & t - 1:\n\tans = 0\nelse:\n\tans = c = 0\n\ts = bin(n + 2)[2:]\n\tl = len(s)\n\tfor i in range(l):\n\t\tif s[i] == '1':\n\t\t\t(m, k) = (l - i - 1, t.bit_length() - c)\n\t\t\tif 0 <= k <= m:\n\t\t\t\tans += fac(m) // fac(k) // fac(m - k)\n\t\t\tc += 1\n\tif t == 1:\n\t\tans -= 1\nprint(ans)\n", "def comb(n, r):\n\tif r > n or r < 0:\n\t\treturn 0\n\tr = min(r, n - r)\n\tresult = 1\n\tfor i in range(1, r + 1):\n\t\tresult = result * (n + 1 - i) // i\n\treturn result\n\ndef F(n, t):\n\tif t == 0:\n\t\treturn 1\n\telif n == 0:\n\t\treturn 0\n\telif n == 1:\n\t\treturn int(t == 1)\n\tm = len(bin(n)) - 3\n\treturn F(n - (1 << m), t - 1) + comb(m, t)\n(n, t) = map(int, input().strip().split())\nT = len(bin(t)) - 3\nif 1 << T != t:\n\tprint(0)\nelse:\n\tprint(F(n + 1, T + 1) - int(t == 1))\n"]

difficulty: HARD

source: codeforces

raw_problem:
C. Maxim and Matrix

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Maxim loves to fill in a matrix in a special manner. Here is a pseudocode of filling in a matrix of size (m + 1) × (m + 1):

Maxim asks you to count, how many numbers m (1 ≤ m ≤ n) are there, such that the sum of values in the cells in the row number m + 1 of the resulting matrix equals t.

Expression (x xor y) means applying the operation of bitwise excluding "OR" to numbers x and y. The given operation exists in all modern programming languages. For example, in languages C++ and Java it is represented by character "^", in Pascal — by "xor".

Input

A single line contains two integers n and t (1 ≤ n, t ≤ 1012, t ≤ n + 1).

Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.

Output

In a single line print a single integer — the answer to the problem.

Examples

Input

1 1

Output

1

Input

3 2

Output

1

Input

3 3

Output

0

Input

1000000000000 1048576

Output

118606527258

question:
Maxim loves to fill in a matrix in a special manner. Here is a pseudocode of filling in a matrix of size (m + 1) × (m + 1):
![image](1.png)
Maxim asks you to count, how many numbers m (1 ≤ m ≤ n) are there, such that the sum of values in the cells in the row number m + 1 of the resulting matrix equals t.
Expression (x xor y) means applying the operation of bitwise excluding "OR" to numbers x and y. The given operation exists in all modern programming languages. For example, in languages C++ and Java it is represented by character "^", in Pascal — by "xor".

Input
A single line contains two integers n and t (1 ≤ n, t ≤ 10^{12}, t ≤ n + 1).
Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.

Output
In a single line print a single integer — the answer to the problem.

Examples
Input
1 1

Output
1

Input
3 2

Output
1

Input
3 3

Output
0

Input
1000000000000 1048576

Output
118606527258

tags: ['Dynamic programming', 'Mathematics', 'Constructive algorithms']

skill_types: ['Dynamic programming']

raw_tags: ['math', 'dp', 'constructive algorithms']

data_split: test


E. LuoTianyi and Cartridge

problem_index: E

time_limit: 3 seconds

memory_limit: 1024 megabytes

note:
The tree from the first example is shown in the statement.
The tree from the second example is shown below:
![image](images/cf_1824_E/3.png)
$$$A = 1, B = 18, C = 1, D = 17$$$, so the cost is $$$\min(1,1) \cdot (18 + 17) = 35$$$.

source: codeforces

raw_problem:
E. LuoTianyi and Cartridge

time limit per test
3 seconds

memory limit per test
1024 megabytes

input
standard input

output
standard output

LuoTianyi is watching the anime Made in Abyss. She finds that making a Cartridge is interesting. To describe the process of making a Cartridge more clearly, she abstracts the original problem and gives you the following problem.

You are given a tree $$$T$$$ consisting of $$$n$$$ vertices. Each vertex has values $$$a_i$$$ and $$$b_i$$$ and each edge has values $$$c_j$$$ and $$$d_j$$$.

Now you are aim to build a tree $$$T'$$$ as follows:

 First, select $$$p$$$ vertices from $$$T$$$ ($$$p$$$ is a number chosen by yourself) as the vertex set $$$S'$$$ of $$$T'$$$.

 Next, select $$$p-1$$$ edges from $$$T$$$ one by one (you cannot select one edge more than once).

 May you have chosen the $$$j$$$-th edge connects vertices $$$x_j$$$ and $$$y_j$$$ with values $$$(c_j,d_j)$$$, then you can choose two vertices $$$u$$$ and $$$v$$$ in $$$S'$$$ that satisfy the edge $$$(x_j,y_j)$$$ is contained in the simple path from $$$u$$$ to $$$v$$$ in $$$T$$$, and link $$$u$$$ and $$$v$$$ in $$$T'$$$ by the edge with values $$$(c_j,d_j)$$$ ($$$u$$$ and $$$v$$$ shouldn't be contained in one connected component before in $$$T'$$$).

  A tree with three vertices, $$$\min(A,C)=1,B+D=7$$$, the cost is $$$7$$$.   Selected vertices $$$2$$$ and $$$3$$$ as $$$S'$$$, used the edge $$$(1,2)$$$ with $$$c_j = 2$$$ and $$$d_j = 1$$$ to link this vertices, now $$$\min(A,C)=2,B+D=4$$$, the cost is $$$8$$$.
Let $$$A$$$ be the minimum of values $$$a_i$$$ in $$$T'$$$ and $$$C$$$ be the minimum of values $$$c_i$$$ in $$$T'$$$. Let $$$B$$$ be the sum of $$$b_i$$$ in $$$T'$$$ and $$$D$$$ be the sum of values $$$d_i$$$ in $$$T'$$$. Let $$$\min(A, C) \cdot (B + D)$$$ be the cost of $$$T'$$$. You need to find the maximum possible cost of $$$T'$$$.

Input

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

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1\le a_i\le 2\cdot 10^5$$$), where the $$$i$$$-th integer represents the $$$a_i$$$ value of the $$$i$$$-th vertex.

The third line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1\le b_i\le 2\cdot 10^5$$$), where the $$$i$$$-th integer represents the $$$b_i$$$ value of the $$$i$$$-th vertex.

Then $$$n-1$$$ lines follow, the $$$j$$$-th of them contains four integers $$$x_j,y_j,c_j,d_j$$$ ($$$1\le x_j,y_j\le n,1\le c_j,d_j\le 2\cdot 10^5$$$) representing the edge $$$(x_j,y_j)$$$ and its values $$$c_j$$$ and $$$d_j$$$ respectively. It's guaranteed that edges form a tree.

Output

Print a single integer — the maximum possible cost of $$$T'$$$.

Examples

Input

3
1 2 2
1 1 2
1 2 2 1
1 3 1 2

Output

8

Input

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

Output

35

Input

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

Output

216

Input

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

Output

7000000

Note

The tree from the first example is shown in the statement.

The tree from the second example is shown below:

$$$A = 1, B = 18, C = 1, D = 17$$$, so the cost is $$$\min(1,1) \cdot (18 + 17) = 35$$$.

question:
LuoTianyi is watching the anime Made in Abyss. She finds that making a Cartridge is interesting. To describe the process of making a Cartridge more clearly, she abstracts the original problem and gives you the following problem.
You are given a tree $$$T$$$ consisting of $$$n$$$ vertices. Each vertex has values $$$a_i$$$ and $$$b_i$$$ and each edge has values $$$c_j$$$ and $$$d_j$$$.
Now you are aim to build a tree $$$T'$$$ as follows:
 -  First, select $$$p$$$ vertices from $$$T$$$ ($$$p$$$ is a number chosen by yourself) as the vertex set $$$S'$$$ of $$$T'$$$. -  Next, select $$$p-1$$$ edges from $$$T$$$ one by one (you cannot select one edge more than once). -  May you have chosen the $$$j$$$-th edge connects vertices $$$x_j$$$ and $$$y_j$$$ with values $$$(c_j,d_j)$$$, then you can choose two vertices $$$u$$$ and $$$v$$$ in $$$S'$$$ that satisfy the edge $$$(x_j,y_j)$$$ is contained in the simple path from $$$u$$$ to $$$v$$$ in $$$T$$$, and link $$$u$$$ and $$$v$$$ in $$$T'$$$ by the edge with values $$$(c_j,d_j)$$$ ($$$u$$$ and $$$v$$$ shouldn't be contained in one connected component before in $$$T'$$$).  ![image](1.png) A tree with three vertices, $$$\min(A,C)=1,B+D=7$$$, the cost is $$$7$$$.  ![image](2.png) Selected vertices $$$2$$$ and $$$3$$$ as $$$S'$$$, used the edge $$$(1,2)$$$ with $$$c_j = 2$$$ and $$$d_j = 1$$$ to link this vertices, now $$$\min(A,C)=2,B+D=4$$$, the cost is $$$8$$$. Let $$$A$$$ be the minimum of values $$$a_i$$$ in $$$T'$$$ and $$$C$$$ be the minimum of values $$$c_i$$$ in $$$T'$$$. Let $$$B$$$ be the sum of $$$b_i$$$ in $$$T'$$$ and $$$D$$$ be the sum of values $$$d_i$$$ in $$$T'$$$. Let $$$\min(A, C) \cdot (B + D)$$$ be the cost of $$$T'$$$. You need to find the maximum possible cost of $$$T'$$$.

Input
The first line contains one integer $$$n$$$ ($$$3\le n \le 2\cdot 10^5$$$) — the number of vertices in the tree $$$T$$$.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1\le a_i\le 2\cdot 10^5$$$), where the $$$i$$$-th integer represents the $$$a_i$$$ value of the $$$i$$$-th vertex.
The third line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1\le b_i\le 2\cdot 10^5$$$), where the $$$i$$$-th integer represents the $$$b_i$$$ value of the $$$i$$$-th vertex.
Then $$$n-1$$$ lines follow, the $$$j$$$-th of them contains four integers $$$x_j,y_j,c_j,d_j$$$ ($$$1\le x_j,y_j\le n,1\le c_j,d_j\le 2\cdot 10^5$$$) representing the edge $$$(x_j,y_j)$$$ and its values $$$c_j$$$ and $$$d_j$$$ respectively. It's guaranteed that edges form a tree.

Output
Print a single integer — the maximum possible cost of $$$T'$$$.

Examples
Input
3
1 2 2
1 1 2
1 2 2 1
1 3 1 2

Output
8

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

Output
35

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

Output
216

Input
5
1000 1000 1 1000 1000
1000 1000 1 1000 1000
1 2 1 1
2 3 1000 1000
3 4 1000 1000
3 5 1000 1000

Output
7000000

Note
The tree from the first example is shown in the statement.
The tree from the second example is shown below:
 ![image](3.png) $$$A = 1, B = 18, C = 1, D = 17$$$, so the cost is $$$\min(1,1) \cdot (18 + 17) = 35$$$.

image_tags: Tree Tree Tree

data_split: test