2025 Winter ESCOM Training Camp, Final Contest
A. Alternating Signs
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$A=[a_1, a_2, ..., a_n]$$$ of $$$n$$$ integers. Find a subsequence $$$a_{i_1}, a_{i_2}, ..., a_{i_k}$$$, such that the sums of elements in that subsequence is maximum possible and the signs of the numbers alternate, i.e. the sign of $$$a_{i_x}$$$ is different from the sign of $$$a_{i_{x+1}}$$$ of all $$$1 \leq x \lt k$$$. Recall that $$$a_{i_1}, a_{i_2}, ..., a_{i_k}$$$ is a subsequence of $$$A$$$ if $$$i_1 \lt i_2 \lt ... \lt i_k$$$.

Note that the subsequence may be empty.

Input

The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) $$$-$$$ length of array A.

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, $$$...$$$, $$$a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$, $$$a_i \neq 0$$$) $$$-$$$ elements of array $$$A$$$.

Output

Print a single integer $$$-$$$ maximum possible sum of elements in a subsequences with given constrains.

Examples
Input
4
7 1 -1 5
Output
11
Input
3
-1 -1 -1
Output
0

B. Collecting Cards
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Manuel is a big fan of "Magic: The Gathering" and is always looking to expand his collection. Recently, he has watched a lot of videos of pack openings, and would like to start doing some himself.

Currently, Manuel doesn't have a lot of money, so he needs to leverage the free "booster" packs that he can get at his local comic book shop. These packs contain a single card, and it can be any of the $$$N$$$ available cards in the market right now. Each card can be uniquely identified by it's 'release" number. All of the $$$N$$$ cards have the same probability to show up in a pack.

Manuel has seen that some videos seem to get more views than others, so he has devised a strategy for his to go viral. He has picked a sequence of $$$K$$$ popular release numbers that he wants to capture in the video. He needs this sequence to show up in a continuous way while he opens packs, that means no gaps or other numbers between the desired sequence.

As to not make a lot of trips to the comic book store, he would like to know what's the expected number of packs that he will need to open until he gets his desired continuous sequence of release numbers.

Input

The first line contains two integers $$$N$$$ and $$$K$$$ ($$$1 \leq N \leq 10^{18}; 1 \leq K \leq 10^6$$$) – the number of available cards and the length of the desired sequence.

Next line contains $$$k$$$ integers $$$a_i$$$ ($$$1 \leq a_i \leq N$$$) separated by a space – the unique identifier assigned to each card.

Output

Print a single integer – the expected number of packs you have to open in order to obtain the desired sequence of cards. It can be shown that this can be represented by $$$P / Q$$$, where $$$P$$$ and $$$Q$$$ are coprime integers. Print the value of $$$P \times Q^{-1}$$$ $$$(mod$$$ $$$10^9+7)$$$

Examples
Input
10 13
1 2 10 5 5 2 4 10 1 5 4 6 7
Output
999930007
Input
2 5
1 1 2 2 1
Output
34

C. Iván Gives a Riddle
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

While explaining the solutions to the Math Contest problems at the Third Winter Training Camp at ESCOM, Iván came up with the following idea to challenge the participants:

You are given two big numbers $$$A$$$ and $$$B$$$ that does not contain the digit $$$0$$$. These numbers can be modified by performing two types of operations:

  1. Swap two adjacent digits in one of the numbers. For example, if $$$B=2468$$$, performing this type of operation can result in $$$B=4268$$$, $$$B=2648$$$, or $$$B=2486$$$. Note that you can perform this operation on $$$A$$$ as well.
  2. Swap the least significant digits of $$$A$$$ and $$$B$$$. For example, if $$$A=348$$$ and $$$B=1234$$$, performing this type of operation will result in $$$A=344$$$ and $$$B=1238$$$.

Find the maximum value of $$$A+B$$$ that you can get by performing the operations above any number of times and in any order. As this number might be huge, print it modulo $$$998244353$$$.

Input

The first line contains two integers $$$A$$$ and $$$B$$$ ($$$1 \leq A,B \lt 10^{10,000}$$$) – the numbers given in the riddle. It is guaranteed that the numbers does not contain any digit $$$0$$$.

Output

Print a single integer – the maximum value of $$$A+B$$$ modulo $$$998244353$$$.

Examples
Input
5
8
Output
13
Input
348
2468
Output
9485
Input
999999937
998244353
Output
3494159

D. Alice Based
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Alice and Bob study at ESCOM, where a popular game called SIM is often played.

The game consists of $$$k$$$ piles of stones, where each pile contains a non-negative number of stones. The two players take turns (Alice goes first), and on each turn, a player must remove a square number of stones from a single pile. The player unable to make a move loses the game.

This game seems boring to them because the winner can be determined in advance if the exact number of stones is known. Since all members of the AlgoRitmo Club (including Alice and Bob) always play optimally, they decided to make the game more interesting.

They have a list $$$P$$$ of positive integers, initially empty. They can perform multiple actions on this list. Alice can add piles of stones. Bob, in turn, can remove any pile from $$$P$$$.

Each time they want to play SIM, they ask Marckess to randomly select stones from the current list $$$P$$$ to include them in the game. Each pile in $$$P$$$ is included in the final list $$$F$$$ with a $$$50\%$$$ chance, independently of the others. However, there is a chance that none of the piles in $$$P$$$ will be selected. To ensure the game always has at least one pile, Alice is allowed to add exactly one specific pile directly to $$$F$$$. This pile does not go through the random selection process and is not part of $$$P$$$.

They want to know the probability that Alice (the first player) will win for each game they play.

Input

The first line contains an integer $$$Q$$$ $$$(2 \leq Q \leq 2 \cdot 10^5)$$$ – the number of actions. The next $$$Q$$$ lines will each contain the description of the actions. The action of Alice and Bob are represented as follows:

  • $$$\mathbf{1\ x}$$$: Alice adds a pile of stones with size $$$x$$$ to the list $$$P$$$ (it is guaranteed that there will be no duplicates).
  • $$$\mathbf{2\ x}$$$: Bob removes a pile of stones with size $$$x$$$ from the list $$$P$$$ (it is guaranteed that this pile is currently in the list).
  • $$$\mathbf{3\ x}$$$: Alice adds a pile of stones with size $$$x$$$ directly to the final list $$$F$$$, and Marckess performs the random process to determine which piles from $$$P$$$ are added to $$$F$$$. Each pile in $$$P$$$ is included in $$$F$$$ independently with a probability of $$$\frac{1}{2}$$$.

The value of $$$x$$$ will be in the range $$$1 \leq x \leq 3 \cdot 10^5$$$ for all actions.

Output

For each query of type 3, print the probability that Alice wins the resulting game after Marckess completes the random selection.

The probability should be printed as the fraction $$$\frac{a}{b}$$$ represented modulo $$$998244353$$$, which means you need to calculate $$$(a \cdot b^{-1}) \mod 998244353$$$ where $$$b^{-1}$$$ is the modular multiplicative inverse of $$$b$$$ modulo $$$998244353$$$

Example
Input
5
1 2
1 3
3 6
2 2
3 9
Output
499122177
1
Note

For the first type-3 query:

At this point, the list $$$P$$$ contains the piles $$$\{2, 3\}$$$. After Marckess performs the random process, the following scenarios are possible:

  1. With probability $$$\frac{1}{4}$$$, the final list $$$F$$$ contains piles $$$\{2, 3, 6\}$$$. It can be proven that Bob always wins if both players play optimally.
  2. With probability $$$\frac{1}{4}$$$, the final list $$$F$$$ contains piles $$$\{2, 6\}$$$. Alice wins.
  3. With probability $$$\frac{1}{4}$$$, the final list $$$F$$$ contains piles $$$\{3, 6\}$$$. Bob wins.
  4. With probability $$$\frac{1}{4}$$$, the final list $$$F$$$ contains only the pile $$$\{6\}$$$. Alice always wins.

Thus, Alice wins with a probability of $$$\frac{1}{2}$$$.

For the second type-3 query:

At this point, the list $$$P$$$ contains the piles $$$\{3\}$$$. The following scenarios are possible:

  1. With probability $$$\frac{1}{2}$$$, the final list $$$F$$$ contains piles $$$\{3, 9\}$$$. Alice wins.
  2. With probability $$$\frac{1}{2}$$$, the final list $$$F$$$ contains only the pile $$$\{9\}$$$. Alice always wins.

Thus, Alice wins with a probability of $$$1$$$.

E. Generalized Sierpiński Carpet
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The Polish mathematician Wacław Sierpiński once designed a famous fractal known as the Sierpiński Carpet, a beautiful and infinitely complex pattern created by recursively removing parts of a square. But what if we could modify the removal pattern?

You have discovered a Generalized Sierpiński Carpet, where the recursion follows a custom $$$3 \times 3$$$ pattern $$$P$$$ consisting of the characters '*' and '.'. Your task is to generate and print this fractal for a given number of recursion steps.

Let's say that $$$S_n$$$ is the Generalized Sierpiński Carpet with $$$n$$$ recursive steps, we define $$$S_n$$$ as follows:

  • $$$S_0$$$ is a grid of size $$$1 \times 1$$$ consisting only of the character '*'.
  • $$$S_n$$$ is a grid of size $$$3^n \times 3^n$$$, built by replacing each '*' symbol with $$$S_{n-1}$$$, and each '.' with a grid of size $$$3^{n-1} \times 3^{n-1}$$$ filled with the character '.'.

Given $$$n$$$ and $$$P$$$, print $$$S_n$$$.

Input

The first line contains a single integer $$$n$$$ ($$$0 \leq n \leq 6$$$) – the number of recursive steps.

Each of the $$$3$$$ lines contains $$$3$$$ characters, where each character is either '*' or '.' – the description of $$$P$$$.

Output

Print $$$S_n$$$.

Examples
Input
2
***
*.*
***
Output
*********
*.**.**.*
*********
***...***
*.*...*.*
***...***
*********
*.**.**.*
*********
Input
2
*.*
.*.
*.*
Output
*.*...*.*
.*.....*.
*.*...*.*
...*.*...
....*....
...*.*...
*.*...*.*
.*.....*.
*.*...*.*
Input
1
*..
.*.
***
Output
*..
.*.
***

F. Dance of Ferrets 2
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a circle drawn on the ground. The circle has $$$n$$$ equally spaced marks on its perimeter. The $$$i$$$-th mark is said to be adjacent to the $$$(i-1)$$$-th and $$$(i+1)$$$-th marks (if they exist). Marks $$$1$$$ and $$$n$$$ are adjacent as well.

$$$n$$$ ferrets numbered form $$$1$$$ to $$$n$$$ will perform a dance on this circle. Initially, the $$$a_i$$$-th ferret is standing on the $$$i$$$-th mark. They will dance for $$$2025!^{2025!}$$$ rounds. If a ferret stands on mark $$$i$$$ at the beginning of a round, it will move to mark $$$p_i$$$ during that round.

Some pairs of ferrets are best friends and don't like being too far from each other. A pair of best friends is happy if they stand in adjacent marks during any round. The pairs of ferrets that are best friends have a particular characteristic: if we consider ferrets as nodes and the best friend relations as edges, the resulting graph forms a tree.

Find two permutations $$$[a_1,a_2,\dots,a_n]$$$ and $$$[p_1,p_2,\dots,a_n]$$$ such that all the pairs of best friends are happy. It can be shown that it is always possible to find such permutations with the given constraints.

Input

The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 3 \cdot 10^5)$$$ – the number of ferrets.

The following $$$n-1$$$ lines contain the pairs of ferrets that are best friends. It it guaranteed that the best friends relations form a tree.

Output

Print the $$$n$$$ space-separated integers $$$a_1,a_2,\dots,a_n$$$ in the first line of the output.

Print the $$$n$$$ space-separated integers $$$p_1,p_2,\dots,p_n$$$ in the second line.

Examples
Input
5
1 2
2 3
3 4
4 5
Output
1 2 3 4 5
1 2 3 4 5
Input
6
3 4
4 5
6 1
1 2
4 1
Output
3 4 5 6 1 2
2 3 1 6 4 5

G. Christmas Present
time limit per test
15 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

El Hurón Legendario was given a magical circular array $$$A=[a_1,a_2,\dots,a_n]$$$ of size $$$n$$$ as a Christmas present last December. Since the array is circular, $$$a_1$$$ and $$$a_n$$$ are adjacent.

For a pair of positive integers $$$x$$$ and $$$y$$$, we say that $$$y$$$ is $$$A$$$-reachable from $$$x$$$ if $$$x$$$ can be transformed into $$$y$$$ by using the following four-step operation any number of times:

  1. Choose an element $$$a_i$$$ of $$$A$$$, such that $$$\gcd(x,a_i) \gt 1$$$.
  2. Choose a prime divisor $$$d$$$ of $$$\gcd(x,a_i)$$$.
  3. Choose a divisor $$$e$$$ of $$$a_i$$$, such that $$$e$$$ is prime or equal to $$$1$$$.
  4. Set $$$x := x \cdot \frac{e}{d}$$$.

After playing with his magical array during a month and using it to transform all the integers less or equal to $$$2025!^{2025!}$$$, El Hurón Legendario wants to save space in its array box. For that reason, he wants to cut some subarray of his circular array and throw away the rest of it. He wants the chosen subarray to be equivalent to the original array. A subarray $$$A'$$$ of $$$A$$$ is equivalent to $$$A$$$, if, for all $$$x,y \in \mathbb{Z}^+$$$, $$$y$$$ is $$$A'$$$-reachable from $$$x$$$ if and only if it is $$$A$$$-reachable from $$$x$$$.

Help El Hurón Legendario find the smallest equivalent subarray he can cut.

Input

The first line contains an integer $$$N$$$ ($$$1 \leq N \leq 2 \cdot 10^5$$$) – the length of the array.

The second line contains $$$N$$$ integers $$$a_1,a_2,\dots,a_N$$$ ($$$1 \leq a_i \leq 2 \cdot 10^5$$$) – the array $$$A$$$.

Output

Print two integers $$$l$$$ and $$$r$$$, representing an equivalent subarray $$$A[l,r]$$$ of minimum length. If $$$l\leq r$$$, then it represents the subarray $$$[a_l,a_{l+1},\dots,a_r]$$$. Otherwise, if $$$l \gt r$$$, it represents the subarray $$$[a_l,\dots,a_N,a_1,\dots,a_r]$$$.

If there are multiple solutions, print any of them.

Examples
Input
5
1 2 1 2 1
Output
2 2
Input
5
45622 1 1 1 43852
Output
5 1
Input
5
2 3 5 6 5
Output
3 4

H. One Two-One Chips (Extreme version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A game invented by Marckess became popular last Donald Knuth Contest. Each person chooses a point in space, and chips will appear in the space. The closest person to a chip will receive one, while the farthest person from the others will lose one. The second closest person will receive two chips, and the second farthest will lose two chips.

However, Tony, Fabian, and Dani's team has obtained relevant information about the appearance of the chips, although it was acquired through somewhat underhanded means.

Despite this, they have only been able to approximate the appearance of each chip independently within a cube with a uniform distribution.

Unfortunately, estimating the expected number of chips obtained per point was an ICPC World Finals-level problem, so they failed to estimate it. Now, they have decided to solve an easier problem: given the side length of a cube, calculate its volume. Is this problem easy enough to solve? Help them find the volume of the cube.

Input

The first line contains a single integer ($$$1 \leq n \leq 20$$$) – the side length of the cube.

Output

Print a single integer – the volume of the given cube.

Example
Input
9
Output
729

I. Mine sweeper
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

9S is on a special mission to locate all hidden mines in an abandoned airport. The airport is represented as an $$$N$$$ × $$$N$$$ grid, where $$$N$$$ is an odd integer. The rows are numbered from $$$1$$$ to $$$n$$$ from top to bottom, and the columns are numbered from $$$1$$$ to $$$n$$$ from left to right. Each cell $$$(i, j)$$$ represents the position at the $$$i$$$-th row and $$$j$$$-th column. There are $$$M$$$ hidden mines in the grid, and each mine emits a unique type of radiation.

To detect the mines, 9S uses a special drone that can sense radiation. The drone follows a specific spiral movement pattern, starting at the top-left corner $$$(1,1)$$$, facing right. It moves according to the following rules:

  1. If the cell in front has not been visited, the drone moves forward.
  2. If the cell in front has been visited or there is no cell ahead (because it is at the edge), the drone turns $$$90^\circ$$$ clockwise and tries to move forward again.
  3. The process continues until every cell in the grid has been visited exactly once.

As the drone moves, it registers the radiation detected in each visited cell. The detected radiation is represented as a binary array of length $$$M$$$. If the $$$i$$$-th bit of this array is $$$1$$$, it means that the drone detected radiation from the $$$i$$$-th mine in that cell; otherwise, it is $$$0$$$.

A mine located at $$$(i_m, j_m)$$$ emits radiation to all cells in the same row or column, meaning that at a cell $$$(i_p, j_p)$$$, the drone will detect its radiation if and only if:

$$$i_p = i_m$$$ or $$$j_p = j_m$$$

To avoid suspicion from the evil machines, 9S limits communication with the drone. The drone will only send data when it is positioned at specific cells that satisfy either of the following conditions:

$$$i_p = j_p$$$ or $$$i_p + j_p = N + 1$$$

When the drone is at one of these cells, it compresses the unsent data before sending it. The compression works as follows:

  1. The drone computes the bitwise AND of all previously recorded readings that have not yet been sent.
  2. It then sends the resulting binary array to 9S.
  3. The reading of the current cell itself is not included in the compression.
  4. If there is no unsent data, the drone sends an array where all bits are set to $$$0$$$.

Given the list of compressed data that the drone sent after completing its journey, your task is to help 9S determine the exact locations of the $$$M$$$ mines.

Input

The first line contains two integers $$$N$$$ and $$$M$$$ $$$(1 \le N \le 1001; 1 \le M \le 1000)$$$ — the size of the matrix and the number of mines in the grid.

The next $$$2N - 1$$$ lines each contain a binary string of length $$$M$$$, representing the compressed data that the drone sent to 9S each time he requested the data.

Output

Print $$$M$$$ lines. The $$$i$$$-th line must contain two integers $$$r$$$ and $$$c$$$, where $$$r$$$ is the row where the $$$i$$$-th mine is located and $$$c$$$ is the column where the mine is located.

Examples
Input
3 3
000
100
100
011
010
Output
1 3
3 1
3 2
Input
1 3
000
Output
1 1
1 1
1 1
Input
5 5
00000
00000
00000
10010
10001
00000
00010
00000
00000
Output
5 1
3 3
3 3
5 4
3 1

J. Leo's Daily Training
time limit per test
3.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Leo is excited about the upcoming ICPC Programadores de América and is preparing a training plan to be ready for the competition. The training plan consists of selecting a list of problems from the popular site HuronCoder.

The site has $$$N$$$ problems numbered from $$$1$$$ to $$$N$$$ and $$$M$$$ tags numbered from $$$1$$$ to $$$M$$$. Each problem can be tagged with any subset of tags (including the empty subset or the set with all the tags). It takes an average of $$$a_i$$$ seconds to solve the $$$i$$$-th problem.

Leo will select a list of problems such that the sum of the average time to solve the problems in the list is exactly $$$s$$$. The list may have repeated problems. We say that the $$$j$$$-th tag is covered by the list if there is at least one problem on it that is tagged with the $$$j$$$-th topic.

As there is a huge number of lists of problems that Leo can choose, so he wants to know the number of lists that he can select to cover each subset of tags. For each subset of tags, help him find the number of lists that cover exactly that subset of tags.

Input

The first line contains three integers $$$N$$$, $$$M$$$, and $$$s$$$ ($$$1 \leq N \leq 10^5$$$, $$$1 \leq M \leq 12$$$ and $$$1 \leq s \leq 10^{18}$$$) – the number of problems in the site and the number of tags.

The following $$$N$$$ contains the descriptions of the problems. The description of a problem contains a bitmask $$$b_i$$$ of length $$$M$$$, followed by an integer $$$a_i$$$ ($$$1 \leq a_i \leq 39$$$) – the tags of the problem and the average seconds it takes to solve it. The $$$j$$$-th bit of $$$b_i$$$ (read from right to left) is $$$1$$$ if the $$$i$$$-th problem is tagged with the $$$j$$$-th tag, and $$$0$$$ otherwise.

Output

Print $$$2^M$$$ integers in a single line. The $$$i$$$-th integers should be the number of lists that cover exactly the subset represented by $$$(i-1)$$$ as a mask (the $$$j$$$-th tag is included in the subset if and only if the $$$j$$$-th least significant bit of $$$(i-1)$$$ is set to $$$1$$$).

As the number of lists is huge, print the answer modulo $$$998244353$$$.

Examples
Input
4 2 2
11 2
10 1
10 2
00 1
Output
1 0 4 1
Input
5 5 20
10000 1
01000 1
00100 1
00010 1
00001 1
Output
0 1 1 1048574 1 1048574 1048574
488905617 1 1048574 1048574 488905617
1048574 488905617 488905617 479169913
1 1048574 1048574 488905617 1048574
488905617 488905617 479169913 1048574
488905617 488905617 479169913 488905617
479169913 479169913 847940114
Note

The second case output is broken into multiple lines so it fits in the output box, but you should print it in a single line.

K. Darkness Rise
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are an incredible Mordekaiser player and a lover of geometry (xD), and you have been fascinated by Morde's passive, it's amazing, a circle.

You know that this passive needs three hits, the same number of points with which you can define a circle, incredible coincidence.

After playing for ten hours straight, you've started to see flashes on the screen, probably due to a drop in FPS, and for a moment, everything was just white dots in your head, and something occurred to you.

How many circles can I define with those points?

More formally, given a set of points, find the number of circles that pass through at least three points of the set. And as you know, League of Legends is a 3D game, so the points will also be 3D, for extra fun ^^.

Input

The first line of the input will contain one integer, $$$n$$$ $$$(3 \leq n \leq 100)$$$, where $$$n$$$ represents the number of points.

The following $$$n$$$ lines will each contain three integers $$$x_i$$$, $$$y_i$$$ and $$$z_i$$$ $$$( x_i, y_i, z_i \leq |10^2|)$$$, representing the coordinates of a point.

No two points will have identical coordinates.

Output

Print one integer — the number of distinct circles that pass through at least three points.

Examples
Input
3
0 0 0
0 2 0
1 1 0
Output
1
Input
4
0 0 0
0 2 0
1 1 0
-1 1 0
Output
1

L. Everyone loves k shortest path problems!
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Not satisfied after authoring two problems that ask for the best $$$k$$$ solutions (HuronForces from Donald Knuth 2021 and Best Tests from ICPC Mexico Repechaje 2024), here is another problem that asks for the best $$$k$$$ solutions:

José Juan is on vacation again and bought $$$n$$$ souvenirs for his two best friends. There are $$$n$$$ types of souvenirs in the souvenir shop. Juan wants to distribute the $$$n$$$ souvenirs between his two friends. He thinks that if he gives the $$$i$$$-th souvenir to his first best friend, it will give him $$$a_i$$$ units of happiness. Similarly, if he gives the $$$i$$$-th souvenir to his other best friend, it would give him $$$b_i$$$ units of happiness.

The distribution of the souvenirs might introduce envy in his friends, so he wants to determine the distributions of souvenirs that have the minimum absolute difference of the total happiness given to his friends.

Find the $$$k=2^{min(n,20)}$$$ distributions with the minimum absolute difference of the happiness of the two friends. Each of the souvenirs must be given to exactly one of the friends.

Input

The first line contains one integer $$$n$$$ ($$$1\leq n \leq 40$$$) $$$-$$$ number of souvenirs in the souvenir shop.

The second line contains $$$n$$$ integers $$$a_i$$$ ($$$|a_i| \leq 10^{16}$$$) – happiness given to the first best friend of José Juan by each souvenir.

The third line contains $$$n$$$ integers $$$b_i$$$ ($$$|b_i| \leq 10^{16}$$$) – happiness given to the second best friend of José Juan by each souvenir.

Output

Print $$$2^{min(n,20)}$$$ integers – the difference of happiness given to José Juan's best of the best distributions of souvenirs sorted in increasing order.

Examples
Input
4
1 2 3 4
4 3 2 1
Output
0 0 0 0 0 0 5 5 5 5 5 5 5 5 10 10
Input
2
-1 10
-1 10
Output
9 9 11 11