The 2017 International Congress of Monsters gathers N monsters coming from all over the world. Their chairman has to solve the following problem: if the *i ^{th} *monster ( 1 ≤ i ≤ N ) has

**Task**

Compute the required sum, modulo *10 ^{ 9} + 7*

**Input Format**

The first line of the input file, **monsters.in** contains the number N.

The second line contains N positive integers, k_{1}, k_{2}, . . ., k_{n} , representing the numbers of fingers of each monster.

**Output Format**

The output file, **monsters.out**, must contain a single positive integer, the requested sum, modulo *10 ^{ 9} + 7*

**Constraints**

- N ≤ 200,000
- k
_{ i}≤1,000,000,000 - The fingers are indexed from 0.

**Subtasks**

Subtask | Score | Additional input constraints |
---|---|---|

1 | 40 | N ≤ 1.000, k_{ i} ≤ 10.000 |

2 | 100 | N ≤ 200.000, k_{ i} ≤ 1.000.000.000 |

**Sample Input **

2

3 7

**Sample Output**

136

**Explanation**

The first monster can obtain 8 numbers:

0 - no finger was lifted;

1 - the index of the lifted finger is 0;

2 - the index of the lifted finger is 1;

3 - the indexes of the lifted fingers are 0 and 1;

4 - the index of the lifted finger is 2;

5 - the indexes of the lifted fingers are 0 and 2;

6 - the indexes of the lifted fingers are 1 and 2;

7 - the indexes of the lifted fingers are 0, 1 and 2;

The second monster can obtain 128 numbers

It is known that the human DNA is represented by an integer number. On a microscopical level, the DNA consists of numerous genes. Considering the binary representation of the corresponding number of the DNA, we notice the following rule: digit 1 on the *i ^{ th}* position indicates the presence of the

**Task**

Generate an array of **2000 **non-negative integers representing the DNAs of a group of adults so that the total number of children with distinct DNAs that can be born from adults belonging to this group is as big as possible. (as big as possible doesn’t mean optimum). The scoring will respect the table below.

**Constraints**

**ATTENTION!**This problem is "output-only". You are expected to upload a .txt file- The demanded array must contain non-negative integers from the range [ 0 , 2
^{ 20}-1 ]. - All children must come from different adults, meaning that any 2 children must have at least one different parent.
- The two parents of a child must be distinct.

**Score**

Score | NR - the number of children with distinct DNAs | |
---|---|---|

1 | 37 | 200,000 ≤ NR ≤ 549,999 |

2 | 74 | 550,000 ≤ NR ≤ 600,000 |

3 | 74 + 1,5 * ( ( X - 600,001 ) * 1 ⁄ 40000 + 1 ) | 600,001 ≤ NR ≤ 999,999 |

4 | 100 | 1,000,000 ≤ NR |

**Example **

Considering that the adults have the following DNAs: 1, 5, 3, 6, 9, 12, the distinct DNAs of the children will be: 1, 0, 4, 2, 8.

Gigel wants to test his cooking abilities and goes to the market to get some supplies. At the market, there are M types of objects sold as promotional packages for a period of N days. On the *i ^{ th} * day, Gigel has two options: he either buys the promotional package available on that day or not. The promotional package is represented by a non-empty subset of the set of the M types of objects and it has a certain price.

**Task**

Knowing M, N, the price and the composition of each of the N promotional packages, find the minimal price that Gigel should pay in order to buy at least one object of each of the M types.

**Input Format**

The first line of the input file, **promotion.in** contains 2 numbers, M and N.

The next N lines describe the N promotional packages in this way: the ( 1 + i )^{ th} line (1 ≤ i ≤ N ) contains *NR* and *P*, which stand for the number of objects in the promotional package from that day and its price. Then, on the same line, there are given *NR* numbers which represent the indexes of the objects that belong to that package.

**Output Format**

In the output file, **promotion.out**print a positive integer number equal to the minimal price that should be paid in order to buy at least one object of every type.

**Constraints**

- 1 ≤ M ≤ 17, 1 ≤ N ≤ 1,000 , 1 ≤ P ≤ 1,000,000
- All numbers found in the input file are positive integers.
- A promotional package shall be bought only completely
- The indexes of the objects that describe a certain package have values from the following set: {1 , 2 , … , M}.
- It is guaranteed that there is a solution for all test cases.

**Subtasks**

Subtask | Score | Additional input constraints |
---|---|---|

1 | 50 | M ≤ 10, N ≤ 100 |

2 | 80 | M ≤ 15, N ≤ 1.000 |

3 | 100 | M ≤ 17, N ≤ 1.000 |

**Sample Input **

5 4

3 10 1 3 2

2 8 1 4

3 11 5 4 3

5 27 1 4 2 3 5

**Sample Output**

21

**Explanation**

The chosen packages are the first and the third ones, thus obtaining a minimal cost of 10+11 = 21. Note that Gigel buys one object of type 1, one object of type 2, two objects of type 3, one object of type 4 and one object of type 5.

After going to a public garden, Antonio returns home, where he finds a string of N non-negative integers and a number X. Feeling bored, he decides to invent a game with this array in N steps. Therefore, at each step, Antonio performs 2 actions:

- He determines all the subsequences of the array whose sums are smaller or equal to X and calculates the arithmetic mean of the sums of such subsequences and their number.
- He circularly permutes the array to the left with one position.

**Task**

Determine the values kept in mind by Antonio at each step.

**Input Format**

The first line of the input file, **comeback.in** contains numbers N and X.

On the second line of this file there are N space-separated elements corresponding to the array.

**Output Format**

The output file, **comeback.out** has N lines:

The i^{ th} line contains two integers separated by a space, the sum of the sums of valid subsequences at step *i * and their number.

**Constraints**

- N ≤ 100,000, X ≤ 1,000,000,000
- The elements of the array are between 0 and 10
^{6}. - A subsequence of the given array consists of elements found on consecutive positions.

**Subtasks**

Subtask | Score | Additional input constraints |
---|---|---|

1 | 40 | N ≤ 1.000 |

2 | 100 | N ≤ 100.000 |

**Sample Input **

3 5

1 2 3

**Sample Output**

14 5

15 5

13 5

**Explanation**

Stage 1. The sum of the sums of valid subsequences: 1 + 2 + 3 + (1 + 2) + (2 + 3)=14

There are 5 valid subsequences.

The array becomes 2, 3, 1.

Stage 2. The sum of the sums of valid subsequences: 2 + 3 + 1 + (2 + 3) + (3 + 1)=15

There are 5 valid subsequences.

The array becomes 3, 1, 2.

Stage 3. The sum of the sums of valid subsequences: 3 + 1 + 2 + (3 + 1) + (1 + 2)=13.

There are 5 valid subsequences.

The array becomes 1, 2, 3.

One morning, Răzvăran decided to invite his two friends, Matthew and Peter, to go for a walk in a well-known public garden. This garden has the shape of a tree with N nodes (indexed from 1 to N) and between N-1 pairs of nodes there are paths which measure 10 meters. In each *i* node, there is an *i* spring. The friends only accept the invitation if the walk respects the following rules: Matthew, a pretentious young man, wants to get to **all** of the springs walking as few meters as possible and Peter, wanting to rise up to the challenge, says that he wants to visit M springs in a **pre-established** order: P_{ 1} , P_{ 2} , … , P_{ m}. Răzvăran now wonders in how many ways they can walk, knowing that both the entrance and the exit are at the first spring, which is at the same time the root of the tree.

**Task**

Determine the number of ways in which the three friends can walk. This number must be printed modulo 10^{ 9}+7

**Input Format**

The first line of the input file, **walk.in** there are two positive integers, N and M, which represent the number of springs of the public garden and the number of springs Peter wants to visit.

The next line contains N-1 numbers T_{ 2} , T_{ 3} , … , T_{ n} representing the parent array corresponding to the tree. On the next line there are M distinct numbers P_{ 1} , P_{ 2} , … , P_{ m}.

**Output Format**

On the first line of the output file, **walk.out** you shall print the required number.

**Constraints**

- 2 ≤ M ≤ N ≤ 400,000
- It is guaranteed that the shape of the public garden is a tree (an acyclic, connected and undirected graph).

**Subtasks**

Subtask | Score | Additional input constraints |
---|---|---|

1 | 20 | 1 ≤ M ≤ N ≤ 10 |

2 | 60 | 1 ≤ M ≤ N ≤ 4.000 |

3 | 100 | 1 ≤ M ≤ N ≤ 400.000 |

**Sample Input **

7 3

1 1 2 2 2 3

5 4 7

**Sample Output**

3 . 4

**Explanation**

The correct ways the three friends can walk are:

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

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

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

Moreover, three invalid walks are :

1 2 5 2 4 2 1 3 7 3 1 (the 6th spring is not visited)

1 2 4 2 5 2 6 2 1 3 7 3 1 (they visit the 4th spring before the 5th one)

1 2 4 2 5 2 6 2 4 2 1 3 7 3 1 (the length of the walk is not minimal)

This is a communication (interactive) problem!

Antonio is known in his city, Barlad, for being the winner of the last edition of
JBOI, a contest for juniors only. As he is a senior from now on, he wants to show his best friend, Zetul, that he can solve harder problems too.

In order to do this, Zetul hid an Easter Egg in the Public Garden, a beautiful park
in their hometown. The Public Garden contains N islands, connected by N-1 bridges, so
that the set of the N islands is beautiful.

Now, Antonio should find the Easter Egg asking Zetul several questions: Antonio
will give Zetul a set of islands and Zetul will tell him whether or not, among the set, there
is the island where the Easter Egg is hidden. The only condition Zetul is asking for is the
set of islands to be beautiful. A set of islands is beautiful if any two islands are connected
by some bridges . More precisely, there is a path of bridges between any two islands from
the set.

You should help Antonio find the Easter Egg, using as few questions as you can,
to show Zetul that Antonio can solve senior problems too!

In a test case, there will be at least one Easter Egg hidden, so make sure your program supports multiple Easter Eggs findings. There will be maximum 60 findEgg calls in a test case, the time limit is for all these calls.

**Task**

You need to implement a function **findEgg**
that determines the island where the
Easter Egg is hidden.

**findEgg (N, bridges)**- N: the number of islands.
- bridges: vector of length N-1; it contains N-1 pairs of islands, so that for every pair there is a bridge connecting the two islands.

You can call a function **query** to help you find the Easter Egg. This function will
return 1, if the egg is found on the islands from the **query** and 0 if not.

**query (islands)**- islands: vector of integers; the set of islands Antonio is giving to Zetul (don’t forget that set of islands must be beautiful).

Subtask | N | Points | Percentage |
---|---|---|---|

1 | N ≤ 16 | 30 | 100%, 0 ≤ Q ≤ 4 |

80%, 5 ≤ Q ≤ 6 | |||

66%, 7 ≤ Q ≤ 10 | |||

40%, 11 ≤ Q ≤ 14 | |||

25%, Q = 15 | |||

15%, Q = 16 | |||

2 | N ≤ 500 | 40 | 100% 0 ≤ Q ≤ 9 |

85%, 10≤ Q ≤11 | |||

66%, 12≤ Q ≤ 45 | |||

3 | N = 512 | 30 | 100% 0 ≤ Q ≤ 9 |

75%, 10≤ Q ≤11 | |||

66%, 12≤ Q ≤ 45 |

**Implementation Details**

You have to submit exactly one cpp file. This file implements **findEgg** as
described above using the following signature: (There will not be a main)
**int findEgg(int N, vector < pair < int, int > > bridges);**

The signature of **query** is as follows: **int query(vector < int > islands)**;

**Example**

For N = 5, and bridges: (1, 2), (1, 3), (2,4), (4,5)

The set {1, 2, 3} is beautiful. The set {1, 2, 4, 5} is beautiful. The set {1, 2, 3, 5} is
**NOT** beautiful(The islands are 1-indexed).

You are given an array V, consisting of N integers V_{1}, V_{2} ... V_{N}.

Your task is to find the result of XOR (1 ≤ i ≤ j ≤ N) (V_{i} + V_{j} )

**Input Format**

The first line contains integer N - the size of the array.

The second linde contains N space-separated integers V_{1} V_{2}, ..., V_{N}.

**Output Format**

The first line contains the required answer.

**Subtasks**

Subtask | Constraints | Scoring |
---|---|---|

1 | 1 ≤ N ≤ 4*10^{3}, 1 ≤ V_{i} ≤ 5 * 10^{8} |
7 points |

2 | 1 ≤ N ≤ 10^{6}, 1 ≤ V_{i} ≤ 4 * 10^{3} |
11 points |

3 | 1 ≤ N ≤ 10^{6}, 1 ≤ V_{i} ≤ 10^{6} |
21 points |

4 | 1 ≤ N ≤ 10^{5}, 1 ≤ V_{i} ≤ 5 * 10^{8} |
38 points |

5 | 1 ≤ N ≤ 10^{6}, 1 ≤ V_{i} ≤ 5 * 10^{8} |
23 points |

**Sample Input **

4

3 9 6 6

**Sample Output**

20

**Note:**

(1, 1) : 3 + 3 = 6

(1, 2) : 3 + 9 = 12

(1, 3) : 3 + 6 = 9

(1, 4) : 3 + 6 = 9

(2, 2) : 9 + 9 = 18

(2, 3) : 9 + 6 = 15

(2, 4) : 9 + 6 = 15

(3, 3) : 6 + 6 = 12

(3, 4) : 6 + 6 = 12

(4, 4) : 6 + 6 = 12

6 ^ 12 ^ 9 ^ 9 ^ ^18 ^ 15 ^ 15 ^ 12 ^ 12 ^ 12 = 20

The scientific committee is in deep trouble: they could come up with a nice task,
but they are not sure they can build the test data for it. The problem statement sounds like
this:

“Being given a string containing only 0s and 1s, compute the number of distinct
non-empty subsequences that appear in it”

Here, by subsequence of a string, we understand a string that can be obtained from
the initial string by erasing some of its characters (possibly none). Two subsequences are
considered different if and only if they differ in at least one place or they have different
lengths. For example, string “101” has 6 different non-empty subsequences: “0”, “1”,
“10”, “01”, “101” and “11”.

Now, the committee could, of course, generate the tests randomly and compute the
answer for each of them with the official source, but this idea doesn’t satisfy the author.
They want to have full control over the output. They want to know, for each value K in a
given file, how many binary strings have **exactly** K different non-empty subsequences
and what is the shortest such string. If there are more strings meeting the requirements,
the committee will be pleased with any such string. As the answer to the first request
might be very big, they want to know just the number modulo 1.000.000.007.

**Input Format**

On the first line of the input file, there will be a number T representing the number of values K that follow. On the next T lines there’ll be the values of K for which you need to answer to the 2 queries described in the statement

**Output Format**

For each value K in the input file, you’ll have to print 2 lines:

On the first line, you should print the number of binary strings that have **exactly** K
different non-empty subsequences modulo 1.000.000.007, or, if you want to skip this
query -1. If you print any number different from -1, we’ll consider that you’ve tried to
answer the question.

On the second line, you should print -1 if you want to skip the query. Otherwise,
you should print L binary digits separated by spaces, digits that should form one of the
binary strings of minimal length that have **exactly** K different non-empty subsequences.

**Subtasks**

There will be 3 subtasks for this problem. You can skip queries **only** in the first
subtask by printing -1s as explained in the Output section.

Subtask | Constraints | Scoring |
---|---|---|

1 | T = 2000 and K takes all the values from 1 to 2000 in order | In order to get a non-zero score, each of your
answers must be either correct, either skipped.
Let A be the number of correct answers to the
first requirement and B the number of correct
answers to the second one. You’ll get: 43 * ( 0.3 * A + 0.7 * B) * 1 / 2000 points |

2 | T ≤ 10, K ≤ 100.000 | 39 points |

3 | T ≤ 10, K ≤ 1.000.000 | 18 points |

**Sample Input **

3

2

3

8

**Sample Output**

2

0 0

4

1 0

-1

1 1 0 0

**Explanation:**

For K = 2, we have exactly 2 strings that with 2 different non-empty
subsequences: “00” (with subsequences “0” and “00”) and “11” (with subsequences “1”
and “11”). To be noted that string “11” has the minimum length too and it would be
accepted by the grader as a correct answer.

For K = 3, we have 4 strings fulfilling the requirement: “10” (with subsequences
“0”, “1” and “10”), “01” (with subsequences “0”, “1” and “01”), “000” (with
subsequences “0”, “00” and “000”), “111” (with subsequences “1”, “11” and “111”)

We skipped the first query for K = 8 and “1100” has exactly 8 different non-empty
subsequences: “0”, “00”, “1” “11”, “110”, “1100”, “10” and “100”.

**This is just an example to clarify the information in the statement. As you can
see, T is not 2000, so this couldn’t be a test from subtask 1, which means that by
skipping a query, we get 0 points.**

Ghiţă is a guy really keen on competitive programming. His favourite activities
are playing with permutations and spending time with his wife, Ana. At their 10^{th}anniversary, Ana gave him a very beautiful permutation as she knew this is the best
present Ghiţă could receive.Let P_{j} be the j ^{th}element of the permutation for every j with 1 ≤ j ≤ N.

Ghiţă was so excited by his present that he began computing the value Q_{i}for each i with 1 ≤ i ≤ N. Q_{i} is defined as the number of increasing subsequences that he could
find in the prefix of length i of his permutation.

More formally, for each i with 1 ≤ i ≤ N, Q_{i} is the number of integer arrays j_{1}, j_{2} ... j_{k} so that 1 ≤ j_{1} < j_{2} < ... < j_{k-1} < j_{k} ≤ i and P_{j1} < P_{j2} < ... < P_{jk}.

He thought that Q, even though it wasn’t a permutation, was pretty nice too.
That’s why he saved it near the permutation P.

Everything was ok until Lică Sămădăul came. He wanted to use Ghiţă’s
surveillance system for immoral purposes and Ghiţa, being a fair man, didn’t help him.
Enraged by Ghiţă’s answer, Lică Sămădăul hired Buză Spartă to help him steal Ghiţă’s
most valuable assets: his permutation and his wife. And so he did.

The next day Ghiţă found out that P was missing and now, the only solution for
Ghiţă to recover the permutation is by using the array Q that he still has. You can guess
that your job is to help Ghiţă recover array P being provided with array Q.

**Input Format**

On the first line of the input there is N, the length of the permutation. On the
second line, separated by spaces, there are Q_{1}, Q_{2}, ... ,Q_{N}.

**Output Format**

On the first and only line of the output, you should print the array P representing the stolen permutation.

**Constraints**

- It is guaranteed that there is exactly one possible answer (only one P has the given Q).
- N ≤ 70.000
- The input size is less than 111 MB.
- We advise you to independently check the running time and the usage of memory of the reading part of your program in order to make sure that the eventual inefficiency of your program is not due to this part, as the reading of the input is not intended to be an impediment in solving this task.

**Scoring**

Subtask | Restriction | T = Number of digits of Q(N) | Maximum input size | Score |
---|---|---|---|---|

1 | N ≤ 9 | - | - | 10 points |

2 | N ≤ 400 | T ≤ 18 | - | 15 points |

3 | N ≤ 700 | - | - | 18 points |

4 | N ≤ 40.000 | T ≤ 171 | 4.5 MB | 17 points |

5 | N ≤ 70.000 | T ≤ 258 | 10 MB | 11 points |

6 | N ≤ 70.000 | T ≤ 314 | 16 MB | 7 points |

7 | N ≤ 70.000 | - | 85 MB | 16 points |

8 | N ≤ 70.000 | - | 111 MB | 6 points |

**Sample Input 1 **

4

1 2 5 6

**Sample Output 1**

3 2 4 1

**Sample Input 2 **

6

1 3 5 9 11 21

**Sample Output 2**

1 6 3 4 2 5

**Explanation:**

In the first example, N = 4 and P = {3, 2, 4, 1}

Q_{1} = 1 because {3} is the only increasing subsequence of {3}

Q_{2} = 2 because {3} and {2} are the only increasing subsequences of {3, 2}

Q_{3} = 5 because {3}, {3, 4}, {2}, {2, 4} and {4} are the only increasing
subsequences of {3, 2, 4}

Q_{4} = 6 because {3}, {3, 4}, {2}, {2, 4}, {4} and {1} are the only increasing
subsequences of {3, 2, 4, 1}.