2016-2017 National Taiwan University World Final Team Selection Contest
A. Hacker Cups and Balls
time limit per test
4 seconds
memory limit per test
512 mebibytes
input
standard input
output
standard output

The dark side of Dreamoon, Ademnoor, wants to play an interesting game with you. Did you hear about the game "cups and balls"? Here is the hacker version of it!

There are n cups and n balls, both are numbered 1, 2, ..., n. At each moment of time, there is exactly one ball in each cup. Initially, ai-th ball is placed in the i-th cup. Admenoor will perform m magic operations on these balls and cups. The i-th operation will sort all the balls in the cups numbered between li and ri, inclusive. The sorting could be performed in either ascending order or descending order. After these m operations, you need to answer which ball is placed in the center cup. We guarantee that n will be an odd integer, so the center cup means the -th cup.

For example, consider n = 5, m = 2 and a = [5, 1, 4, 2, 3]. If the first operation is to sort the balls in the cups numbered between 1 and 4 in ascending order, then a would become [1, 2, 4, 5, 3]. If the second operation is to sort the balls in the cups numbered between 2 and 5 in descending order, then a would become [1, 5, 4, 3, 2]. In this example, the number of the ball in the center cup after all operations is 4.

Input

The first line of input contains two integers n and m. The following line contains n integers a1, a2, ..., an. Each of the following m lines contains two integers li and ri. If li < ri, Admenoor will sort that balls in ascending order in this operation; otherwise, the balls will be sorted in descending order in this operation.

  • 1 ≤ n ≤ 99 999
  • n is an odd integer
  • 0 ≤ m ≤ 105
  • 1 ≤ ai ≤ n
  • is a permutation of 1, 2, ..., n
  • 1 ≤ li, ri ≤ n
Output

Output a single line with the number of the ball in the center cup after all operations.

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

B. Bored Dreamoon
time limit per test
1 second
memory limit per test
512 mebibytes
input
standard input
output
standard output

Dreamoon serves in the military this year. Everything in the military is boring. In order to make military life more interesting, Dreamoon decided to transform some of his military experiences into programming competition problems.

The leaders usually order soldiers to stand in several rows ordered by their heights. The rules of arrangement of soldiers are as follows:

  • If two soldiers A and B stand in different rows, and A's row is in front of B's row, A is shorter than B.
  • If two soldiers A and B stand in the same row, and A is to the right of B, A is shorter than B.
  • For any two rows, the difference between the number of soldiers in them is at most 1.
  • For any two rows, the number of soldiers in the front row is equal to or larger than the number of soldiers in the back row.

After Dreamoon noticed these properties, the following problem came to his mind:

For two different soldiers A and B, we say B is right front of A if A's row is NOT in front of the B's row, and the number of soldiers to the right of B in B's row is not larger than the number of soldiers to the right of A in A's row.

You don't know how many soldiers there are in total, and you don't know how many rows these soldiers are arranged into. But you have some information about certain N soldiers, numbered from 1 through N. You are given the heights of these soldiers. And for any two distinct numbers i and j, you know whether soldier j is right front of i. Please inspect whether there exists at least one possible configuration satisfying the given information. If possible, you should calculate the minimum number of soldiers in the first row (the row in front of every other row).

Input

The first line of input contains one integer N indicating that you have information of N soldiers. The second line of input consists of N integers h1, h2, ..., hN. Here, hi indicates the height of i-th soldier. Note that the unknown heights of the soldiers are allowed to be non-integers.

Each of the following N lines contains N characters. The j-th character in the i-th of these lines is '1' if soldier j is right front of soldier i; otherwise, it is '0'.

  • 2 ≤ N ≤ 103
  • 1 ≤ hi ≤ 109
  • all hi are distinct
  • for all i in 1, 2, ..., N
Output

Output one number indicating the minimum possible number of soldiers in the first row (the row in front of every other row). If there is no possible configuration satisfying the given information, output  - 1 instead.

Examples
Input
3
1 2 3
000
000
000
Output
3
Input
3
1 2 3
000
100
110
Output
1

C. Crazy Dreamoon
time limit per test
1 second
memory limit per test
512 mebibytes
input
standard input
output
standard output

Dreamoon likes algorithm competitions very much. But when he feels crazy because he cannot figure out any solution for any problem in a competition, he often draws many meaningless straight line segments on his calculation paper.

Dreamoon's calculation paper is special: it can be imagined as the plane with Cartesian coordinate system with range [0, 2000] × [0, 2000] for the coordinates. The grid lines are all lines of the form x = c or y = c for every integer c between 0 and 2000, inclusive. So, the grid contains 2000 × 2000 squares.

Now, Dreamoon wonders how many grid squares are crossed by at least one of the lines he drew. Please help Dreamoon find the answer. Note that, to cross a square, a segment must contain an interior point of the square.

Input

The first line of input contains an integer N denoting the number of lines Dreamoon draw. The i-th line of following N lines contains four integers xi1, yi1, xi2, yi2, denoting that the i-th segment Dreamoon drew is a straight line segment between points (xi1, yi1) and (xi2, yi2).

  • 1 ≤ N ≤ 2 × 103
  • 0 ≤ xi1, yi1, xi2, yi2 ≤ 2 × 103
  • the lengths of all line segments in input are non-zero
Output

Output one integer on a single line: how many grid squares are crossed by at least one of the line segments which Dreamoon drew.

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

D. Forest Game
time limit per test
4 seconds
memory limit per test
512 mebibytes
input
standard input
output
standard output

Consider the following boring game about removing nodes from a forest. Initially, the forest contains only one tree with N nodes, and your initial score is 0. The game then goes as follows:

  1. If the forest is empty, the game is finished. Otherwise, you choose one node from the current forest uniformly at random.
  2. Your score increases by the size of the tree which your chosen node belongs to.
  3. Remove your chosen node and all edges connected to this node. Then proceed to step 1.

Please calculate the expected value of your final score multiplied by N!, modulo 109 + 7.

Input

The first line of input contains one integer N indicating the number of nodes in the initial tree.

Each of the following N - 1 lines contains two integers x and y, indicating that x-th node and y-th node are connected by an edge in the given tree. The nodes are numbered from 1 to N.

  • 1 ≤ N ≤ 105
  • 1 ≤ x, y ≤ N
  • the given graph is a tree
Output

Output one number: the expected value of the final score of this boring game multiplied by N!, modulo 109 + 7.

Examples
Input
2
1 2
Output
6
Input
3
1 2
2 3
Output
34

E. Lines Game
time limit per test
2 seconds
memory limit per test
512 mebibytes
input
standard input
output
standard output

Consider the following game about removing N straight line segments on the plane. The segments are numbered from 1 to N. The i-th segment connects points (0, i) and (1, pi), where the numbers p1, p2, ..., pN are a permutation of numbers from 1 to N. Your are also given N positive integers v1, v2, ..., vN. On each step, you can select any segment i which is not removed yet, pay vi dollars, and then remove the i-th segment and all segments intersecting with it. Note that you MUST remove all segments which intersect with i-th segment.

The purpose of this game is to remove all segments while spending the minimum possible sum of dollars. Please answer how much you need to spend when you play the game with best strategy.

Input

The input consists of three lines. The first line contains an integer N. The second line consists of N integers p1, p2, ..., pN. The third line consists of N integer v1, v2, ..., vN.

  • 1 ≤ N ≤ 105
  • is a permutation of 1, 2, ..., N
  • 1 ≤ vi ≤ 2 × 104
Output

Output only one number indicating the minimum possible sum of dollars required to remove all segments.

Examples
Input
4
2 1 4 3
1 2 3 4
Output
4
Input
4
1 2 3 4
1 2 3 4
Output
10

F. Lonely Dreamoon 2
time limit per test
1 second
memory limit per test
512 mebibytes
input
standard input
output
standard output

Dreamoon, who doesn't have a girlfriend, often goes for a walk along some streets in Taipei while thinking about problems from algorithm competitions. Unfortunately, there are so many couples acting lovey-dovey on the street that Dreamoon can not focus on thinking about those problems.

One day, despite the love birds everywhere, Dreamoon discovered a problem input containing an integer sequence: a1, a2, a3, ..., aN.

Dreamoon thought: because I'm single, every pair of consecutive numbers should have a large difference! This is, Dreamoon wants to reorder the sequence to make the value as large as possible.

So Dreamoon turned on Drazil, who does have a girlfriend, and forced Drazil to fulfill the above condition by reordering the integer sequence. Please help poor Drazil  > _ < 

Input

The input consists of two lines. The first line contains an integer N. The second line consists of N integers a1, a2, ..., aN.

  • 2 ≤ N ≤ 2 × 105
  •  - 109 ≤ ai ≤ 109
Output

Output a single line consisting of N integers, denoting the integer sequence a after reordering. For this reordering, the value must be the largest possible among all reorderings of the input sequence. If there are several possible answers, output any one of them.

Examples
Input
3
3 1 5
Output
3 5 1
Input
4
-1 -1 1 1
Output
1 -1 1 -1

G. Dreamoon and NightMarket
time limit per test
1 s
memory limit per test
512 mebibytes
input
standard input
output
standard output

After moving to Taipei, Dreamoon always goes to dinner at Jinmei Night Market. There are N kinds of food sold at Jinmei Night Market. These foods are numbered from 1 to N. The price of one piece of i-th food is pi.

Every night, Dreamoon will choose a non-empty set of foods and eat one piece of each food in this set. Dreamoon likes new things. So he won't choose the same set in two different nights. Besides this, because Dreamoon is a poor boy, each night, he will choose the cheapest food set that he didn't choose before.

Now, you are given a positive integer K. Can you tell Dreamoon which set of foods he will choose on K-th day? You only have to tell him how much he will spent on this day.

Input

The input consists of two lines. The first line contains an integer N. The second line consists of N integers p1, p2, ..., pN.

  • 2 ≤ N ≤ 2 × 105
  • 1 ≤ K ≤ min(106, 2N - 1)
  • 1 ≤ pi ≤ 108
Output

Output one number indicating how much Dreamoon will spend on food on K-th day.

Examples
Input
5 30
4 2 1 16 8
Output
30
Input
4 5
1 1 2 2
Output
2

H. Split Game
time limit per test
1 second
memory limit per test
512 mebibytes
input
standard input
output
standard output

Consider the following game about splitting a simple polygon with N vertices on a plane. The purpose of this game is using a straight line which passes through the origin to split the given simple polygon into as many non-zero area regions as possible. Please finish the game with the best result possible.

Input

The input consists of N + 1 lines. The first line contains an integer N. The i-th of the following N lines consists of two integers xi and yi indicating the vertices of the given polygon in counter-clockwise order. Also, the actual lower bound on N is 3.

  • 1 ≤ N ≤ 105
  • 1 ≤ xi, yi ≤ 109
  • if i ≠ j, then (xi, yi) ≠ (xj, yj)
  • the vertices are given in counter-clockwise order
  • the polygon is simple: its sides have no common points except the vertices
Output

Output one integer: the maximum number of non-zero area regions into which the given polygon can be split by a single line passing through the origin.

Examples
Input
4
1 1
2 1
2 2
1 2
Output
2
Input
6
2 1
4 2
8 4
4 8
2 4
1 2
Output
2
Input
10
1 1
3 1
3 3
5 3
5 5
4 5
4 4
2 4
2 2
1 2
Output
5
Note

I. Tree Game
time limit per test
1 second
memory limit per test
512 mebibytes
input
standard input
output
standard output

Consider the following game about coloring edges in a tree.

You are given a tree. Initially, the color of all edges is white. Let a valid path be a simple path such that all its edges are white, and the two endpoints are leaves in the tree. On each step of this game, you can choose a valid path and paint all its edges black. You cannot stop your game until you cannot find any valid path.

The purpose of this game is to use the minimum number of steps to complete the game. Please find the minimum number of steps for the given tree.

Input

The first line of input contains one integer N indicating the number of nodes in the given tree.

Each of the following N - 1 lines contains two integers x and y indicating that x-th node and y-th node are connected by an edge in the given tree. Nodes are numbered from 1 to N.

  • 2 ≤ N ≤ 105
  • 1 ≤ x, y ≤ N
  • the given graph is a tree
Output

Output one integer: the minimum number of steps required to complete the game on the given tree.

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

J. Zero Game
time limit per test
1 second
memory limit per test
512 mebibytes
input
standard input
output
standard output

You are given one string S consisting of only '0' and '1'. You are bored, so you start to play with the string. In each operation, you can move any character of this string to some other position in the string. For example, suppose . Then you can move the first zero to the tail, and S will become '0100'.

Additionally, you have Q numbers K1, K2, ..., KQ. For each i, you wonder what can be the maximum number of consecutive zeroes in the string if you start with S and use at most Ki operations. In order to satisfy your curiosity, please write a program which will find the answers for you.

Input

The first line of input contains one string S. The second line of input contains one integer Q. Each of the following Q lines contains one integer Ki indicating the maximum number of operations in i-th query.

  • 2 ≤ N ≤ 106
  • the length of S is exactly N characters
  • S consists of only '0' and '1'
  • 1 ≤ Q ≤ 105
  • N × Q ≤ 2 × 107
  • 1 ≤ Ki ≤ 106
Output

For each query, output one line containing one number: the answer for this query.

Example
Input
0000110000111110
5
1
2
3
4
5
Output
5
8
9
9
9