After its citizens were fully vaccinated, the COVID-19 pandemic on the cat planet was finally defeated, and life is gradually getting back to normal. To celebrate the victory, the royalties of cat planet organized a sport event with many different games, one of which is called Permeowtation (courtesy of Neko) with the rules as follows:

Initially, the athlete is given two permutations ~a~ and ~b~, both having length ~n~. The athlete needs to merge these two permutations together to make an array ~c~ consisting of ~2 \cdot n~ elements with the following procedure:

• Initially, array ~c~ is empty.

• The athlete performs ~2\cdot n~ steps. At each step, the athlete chooses either array ~a~ or array ~b~, erase the first element of the chosen array, and append this element into ~c~. Note that the chosen array must contain at least one element.

The athlete will be awarded a prestigious medal from the cat planet sports federation, if the array ~c~ created by the athlete contains no two consecutive elements of equal value. In other words, the athlete needs to create an array ~c~ satisfying ~c_i \ne c_{i + 1}~ for every ~1 \le i < 2 \cdot n~.

Mike, a young but enthusiastic athlete in this sport, has tried very hard to prepare for the best. But before the stage, Mike felt nervous and suddenly forgot the best strategy to win the game. Please help Mike play this game and win a medal!

Definition. A permutation is an array consisting of ~n~ distinct integers from ~1~ to ~n~ in arbitrary order. For example, ~[2,3,1,5,4]~ is a permutation, but ~[1,2,2]~ is not a permutation (~2~ appears twice in the array) and ~[1,3,4]~ is also not a permutation (~n=3~ but there is ~4~ in the array)

Input

The first line contains a single integer ~n~ (~2 \le n \le 10^5~), the length of ~a~ and ~b~.

The second line contains ~n~ distinct integers ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le n~).

The third line contains ~n~ distinct integers ~b_1, b_2, \ldots, b_n~ (~1 \le b_i \le n~).

Output

Output ~2n~ characters a or b, with the ~i~-th character denoting the array that should be chosen in the ~i~-th step.

It can be shown that the answer always exists with the given constraints.

Scoring

• Subtask 1 (~15~ points): ~n = 2~

• Subtask 2 (~15~ points): ~n \le 10~

• Subtask 3 (~20~ points): No additional constraints

The total score for this problem is ~50~.

Sample Input 1

3
1 2 3
3 2 1

Sample Output 1

abaabb

Sample Input 2

2
2 1
1 2

Sample Output 2

baab

Notes

In the first example, array ~a~ has the value ~[1, 2, 3]~ and array ~b~ has the value ~[3, 2, 1]~.

With the given example output, array ~c~ has the value ~[1, 3, 2, 3, 2, 1]~.

During recess, a group of ~n~ students go outside for rope skipping. Each turn, two of the students will turn the rope, and one student jumps. The two rope turners will hold two ends of the rope, one spinning clockwise, the other counter-clockwise, so that the rope periodically hits the ground, and passes over the skipper's head. The skipper stands in between the two rope turners, and must jump when the rope hits the ground. If the rope hits the skipper's leg, the skipper loses.

All ~n~ students are very strong and flexible, their flexibility are ~c_1, c_2, \ldots, c_n~.

If the ~i~-th student is the skipper, then for ~c_i~ seconds, their feet will be on the ground. Afterwards, they jump, and their feet will be off the ground for the next ~c_i~ seconds. This process repeats. For example, if ~c_i = 3~:

• On seconds ~1, 2, 3~ their feet is on the ground.

• On seconds ~4, 5, 6~ their feet is off the ground.

• On seconds ~7, 8, 9~ their feet is on the ground.

• On seconds ~10, 11, 12~ their feet is off the ground.

• ~\ldots~

If the ~u~-th and ~v~-th students are chosen to be the rope turners, then the rope hits the ground at precisely the seconds that are multiples of ~gcd(c_u, c_v)~, in which ~gcd(x, y)~ denotes the greatest common divisor of two positive integers ~x~ and ~y~. For example, if ~c_u = 6~ and ~c_v = 8~, ~gcd(6, 8) = 2~, therefore the rope will hit the ground at seconds ~2, 4, 6, 8, 10, \ldots~

You are given the flexibility of all ~n~ students. For the ~i~-th student, calculate how many pairs of students ~u~ and ~v~ (~u < v~), such that if the ~i~-th student is the skipper, then they will never lose.

Input

The first line contains a single integer ~n~ (~3 \le n \le 10^6~), the number of students.

The second line contains ~n~ integers ~c_1, c_2, \ldots, c_n~ (~1 \le c_i \le 10^6~), the flexibility of the ~n~ students.

Output

Output ~n~ integers, the ~i~-th of which is the number of pairs of students such that if the ~i~-th student is the skipper, they will never lose.

Scoring

• Subtask 1 (~65~ points): ~n \le 100~

• Subtask 2 (~65~ points): No additional constraints

The total score for this problem is ~130~.

Sample Input 1

3
1 6 8

Sample Output 1

1 0 0

Sample Input 2

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

Sample Output 2

15 3 1 0 0 0 0 0 0 0 0 0

Notes

In the first example:

• If the first student is the skipper, their feet do not touch the ground at seconds ~2, 4, 6, 8, \ldots~ because ~c_1 = 1~. The rope turners may be the second and third student, due to ~c_2 = 6, c_3 = 8~, ~gcd(6, 8) = 2~, and the moments that the rope touches the ground are seconds ~2, 4, 6, 8, \ldots~.

• If the second student is the skipper, they'd lose if the other two were the rope turners, because ~gcd(1, 8) = 1~, thus the rope touches the ground at every integer seconds. The same thing happens if the third student is the skipper

Fun fact: The game described in the statement is more similar to Double Dutch than Skipping rope, but played with a single rope.

Lộc likes dark cyan, because of that, when Lộc registers his first account on a mysterious Online Judge, he chose the nickname darkcyan. Unfortunately, this nickname was taken. The system recommends Lộc a couple of other nicknames, some of which are darkcyan_no1, darkcyan_pro and darkcyan_vip, none of which Lộc liked at all. After spending a few eternities pondering, the nickname chosen by Lộc was darkkcyan, very similar to the initial nickname, only duplication the k. This nickname turns out wasn't taken! So it became Lộc's new nickname for many other different Online Judges.

Lộc finds changing nicknames like this interesting, and he applies this idea to create an entirely novel nickname suggestion system! For a nickname that's represented by a string with ~k~ characters ~t_1 t_2 \ldots t_k~, the system can change the nickname using the following operation several (possibly zero) times:

• The system selects an integer ~i~ (~1 \le i \le k~), then inserts the character ~t_i~ right after position ~i~. The new character's index is ~i + 1~ and the index of every following characters are increased by one. The length of the new nickname will be ~k + 1~.

For example, given the nickname darkcyan, with one operation, the system can generate the nicknames darkkcyan, ddarkcyan and darkcyann, and with three operations the nicknames ddaarrkcyan, darkkkkcyan or ddarkkcyann can be generated.

For the sake of optimization, the system needs to use the least operations to change a nickname, such that the nickname has never appeared in the system, to recommend for the user.

Lộc thinks it's a pity if there's no existing nickname recommendation system like this. So he decides to implement this system for the social network Virtual Network for Online Intercommunication (VNOI) that he's developing. On VNOI there are currently ~n~ users, the ~i~-th of which has the nickname ~S_i~. Lộc wants to know, for each nickname ~S_i~, if there is a new user who attempts to register with this nickname, how many operations does it take for this system to generate a new, unused username on VNOI. As Lộc is a very busy developer, he needs your help to solve this problem.

Given the list of nicknames of the ~n~ users on the system, for each nickname ~S_i~, calculate the least number of operations to turn ~S_i~ into a new, unused nickname, on the system.

Input

The first line contains an integer ~n~ (~1 \le n \le 10^6~) the number of VNOI users.

The ~i~-th line out of the next ~n~ lines contains a single string ~S_i~ (~1 \le |S_i| \le 10^6~, ~S_i~ consists only of lowercase English letters), the nickname of the ~i~-th user.

The total length of all the nicknames do not exceed ~10^6~. Furthermore, no two nicknames are the same.

Output

Output ~n~ lines. The ~i~-th of which denoting the least number of steps to turn ~S_i~ into a nickname that has not appeared on the system.

Scoring

• Subtask 1 (~55~ points): All the characters within one nickname are the same.

• Subtask 2 (~75~ points): No additional constraints.

The total score for this problem is ~130~.

Sample Input 1

3
aaa
a
aa

Sample Output 1

1
3
2

Sample Input 2

3
ab
aab
abb

Sample Output 2

2
1
1

FireGhost and friends are planning to travel to VNOI city!

There are ~n~ famous landscapes in the city. As for planning, the friends need to decide the list of the landscapes that they are going to visit. Therefore there are ~2^n~ different travel plans, from not visiting any landscapes at all, to visiting all of the landscapes.

However, not every plan will make FireGhost's friends happy. He has ~m~ friends. Each of the friends has a wishlist, and each entry in the list will either be "I want to visit the ~p~-th place" or "I don't want to visit the ~p~-th place". Fortunately, everyone is easy-going: a friend will be happy if the plan satisfies at least one entry in their wishlist.

FireGhost is curious about the number of plans that make all of his friends happy. Can you help him?

Input

The first line contains two integers ~n~ and ~m~ (~1 \le n \le 10^5~, ~1 \le m \le 20~) — the number of landscapes and the number of friends, respectively.

The ~i~-th of the next ~m~ lines starts with an integer ~k~ (~1 \leq k \leq n~) — the number of entries in the wishlist of the ~i~-th friend, followed by ~k~ integers ~a_1, a_2, \ldots, a_k~ (~1 \le |a_j| \le n~)  — the entries' description:

• if ~a_j > 0~, the ~i~-th friend wishes to visit the ~a_j~-th landscape,

• otherwise, if ~a_j < 0~, the ~i~-th friend wishes not to visit the ~|a_j|~-th landscape.

It is guaranteed that ~|a_{u}| \neq |a_{v}|~ for all ~1 \le u < v \le k~.

Output

Output the number of plans that make all of FireGhost's friends happy, modulo ~10^9 + 7~.

Scoring

• Subtask 1 (~30~ points): ~n \leq 20~ and ~m \leq 5~

• Subtask 2 (~94~ points): ~n \leq 10^3~ and ~m \leq 15~

• Subtask 3 (~180~ points): No additional constraints.

The total score for this problem is ~304~.

Sample Input 1

4 2
2 1 -4
1 3

Sample Output 1

6

Sample Input 2

7 1
2 -2 6

Sample Output 2

96

Sample Input 3

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

Sample Output 3

36

Notes

In the first test case, only these plans (the landscapes lists) can make all of the friends happy:

1. ~\{3\}~,

2. ~\{1, 3\}~,

3. ~\{2, 3\}~,

4. ~\{1, 2, 3\}~,

5. ~\{1, 3, 4\}~,

6. ~\{1, 2, 3, 4\}~.

The other plans will make somebody unhappy. For example:

• The plan ~\{3, 4\}~ will not make the first friend happy, because he does not want to visit the ~4~-th landscape.

• The plan ~\{1\}~ will not make the second friend happy, because he the only place he wants to visit is the ~3~-rd landscape.

• The plan ~\{4\}~ will make nobody happy.

An undirected graph is called a dumbbell if its vertices can be partitioned into ~2~ parts, such that:

• Each pair of vertices in the same part are connected by an edge.

• There exists exactly one edge that connects two vertices in different parts.

The following graphs are dumbbells:

The following graphs are not dumbbells:

The leftmost graph cannot be partitioned into two parts connected by an edge. In the middle graph, there is one part in which not all pairs of vertices are connected by an edge. The rightmost graph is not connected.

You are given an undirected graph with ~N~ vertices and ~M~ edges. The graph is simple: There is no self-loops, and there is no more than one edge between any pair of vertices. Calculate the least number of edges needed to add into the graph so that it becomes a dumbbell.

Input

The first line contains two integers ~n~ and ~m~ (~2 \le n \le 10^5~, ~0 \le m \le 10^5~), the number of vertices and edges of the given graph, respectively.

Each of the following ~m~ lines contain two integers ~u~ and ~v~ (~1 \le u, v \le n~, ~u \ne v~), denoting an edge between ~u~ and ~v~.

It is guaranteed that no two edges connect the same pair of vertices.

Output

Output a single integer, the least number of edges needed to add into the graph so that it becomes a dumbbell.

If there is no way to add edges to make the graph a dumbbell, output ~-1~.

Scoring

• Subtask 1 (~125~ points): ~n \le 500~

• Subtask 2 (~285~ points): No additional constraints

The total score for this problem is ~410~.

Sample Input 1

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

Sample Output 1

0

Sample Input 2

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

Sample Output 2

5

Sample Input 3

3 3
1 2
2 3
3 1

Sample Output 3

-1