Description

You are a great adventurer investingating the abyss.

The abyss can be described as a set of nodes, where each node may connect to some other nodes.

The abyss is known to imprison any creature to deeper levels, i.e., if it is possible to reach node v from node u, then it is impossible to reach node u from node v. However, you are not some ordinary creature, so you are not affected by this during your journey.

The abyss has only one entrance, node 1, and there is exactly one simple path (a path without visiting duplicate nodes) from node 1 to any other node.

You are curious for each node, the number of reachable nodes.

Input

N

X_1 Y_1

X_2 Y_2

...

X_{N-1} Y_{N-1}

(N is a positive integer not exceeding 100000, and X_i, Y_i are integers between 1 and N, it is guaranteed that no circular relationship will occur)

(X_i Y_i means there is a path between X_i and Y_i, and the direction is X_i to Y_i).

Output

A_1 A_2 A_3 ... A_N

, where A_i is the number of reachable nodes (excluding i itself) from node i.

Do put a newline character after the last number.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

2048 is a well-known game, if you hasn't play it before, play it now!

How to play 2048:
You can choose to move all the tiles to 4 directions: up, down, left, right. Tiles with the same number merge into one when they touch and the value becomes their sum. After that, the board will radomly gernerate new tile on the tile that is empty. Game ends when you get the tile with value 2048 or their's no way to move. For more information, please refer to link.

Now you're asked to write a program to move/merge the tiles with the given board and direction to move. You don't have to implement the part that generates new tiles randomly.

Input

Input contains multiple testcases, you have to read the input until EOF.
Each testcase contains a 4 by 4 grid representing the board of the game. The number on it is less than 2048 and it should be a power of 2 except 1 and 0 represents empty.

Output

Output the board after moving up/down/left/right respectively.
If nothing happen when moving on that direction, output "Invalid".

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There is a row with N blocks. Blocks are numbered from left to right in 1-based indexing. The value of the i-th block is a_i.

You are on the 1-th blocks now. For convenience, let's call the block you currently on as happy block. Of course you can only be on one block at the same time.

Now you need to execute Q operations. There are three kinds of operations:

1. Move to the blocks which is on the left/right to happy block.
2. Output the value of happy block.
3. Remove the block in the middle of all the blocks. If there are not only one blocks in the middle(i.e the number of blocks is an even number), remove the one which is closer to the left side. If the removed block is happy block, you would move to the block which is on the right to happy block before removing.

It's guaranteed that:

1. The block you move to must exist.
2. The third type of operations appears at most N - 1 times(i.e there must be at least one block all the time).

Note: be careful of the efficiency of your strategy.

Input

The first line contains one integer N (1 ≤ N ≤ 5 x 10⁵) – the number of blocks.

The second line contains N integers a₁, a₂, ..., a_N (0 ≤ a_i ≤ 10⁹) – the value of each block.

The third line contains one integer Q (1 ≤ Q ≤ 5 x 10⁵) – the number of operations you need to execute.

Then Q lines follow. The i+3-th line contains one integer type_i (1 ≤ type_i ≤ 3) – the type of operations you need to execute. If type_i = 1 then one integer dir (dir = -1 or dir = 1) follows – -1 for moving to the block which is on the left to happy block and 1 for the right.

It's guaranteed that:

• The 1st testcase must be as same as Sample below
• For the first five testcases: 1 ≤ N, Q ≤ 1000

Output

For every 2nd type operations, output the value of happy block then.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

This is a partial judge problem.

Given one linked list, you are asked to complete the following two tasks in two different functions:

(1) Partial sort

Given an integer x, you need to put every node which value < x to the front of the linked list.

For example, if x = 4, 7->2->4->1->3->5 will become 2->1->3->7->4->5 after partial sorting.

(Note: You can't change the original relative position between the nodes which value < x and value >= x.)

(2) Split and Swap

Given two integers a and b , you can get two groups: (1) index 0 to index a , (2) index b to index N-1.

All you need to do is swap the two groups. (N is the length of the given linked list)

For example, if a = 1, b = 4, 1->2->3->7->4->5 will become 4->5->3->7->1->2 after the operations.

function.h:

typedef struct _Node {
    int data;
    struct _Node *next;
} Node;

Node* Partial_sort(Node*, int);

Node* Split_and_Swap(Node*, int, int);

You only need to implement the two functions below in function.h.

Input

First line contains four integers which denote N (the length of given linked list), x, a, b respectively.

(6 <= N <= 10, 1 <= x <= 7, 0 <= a < b <= N-1)

Second line contains N integers which denote the given linked list.

Output

One linked list result after the two operations.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

Yazmonkey is an outstanding hacker, he's paid to get the scoreboard of the final exam of Introduction to Programming since the original scoreboard is blocked.

You're Yazmonkey's apprentice, and Yazmonkey wants to test your ability, so he wrote a program to crawl all the submissions from the final exam and asked you to generate the scoreboard. If you failed this mission, Yazmonkey will punch you in face and expel you.

Reference:
Web Crawler
HTML

You don't have to know how to write HTML, you just have to parse the information that is useful from the input, and output the scoreboard.
The first test case is the Sample Input.

Input

Input contains the raw data of the HTML table of all the submisstions. Guarantee that all html tag meets the following format: 

<tagname>Content goes here...</tagname>

First ten line is as follow, but it may have more/less spaces or even no space between the content and the html tag or infront/behind the html tag. 

<table>
  <thead>
    <tr>
      <th>Submit Time</th>
      <th> User</th>
      <th>Problem </th>
      <th>Status</th>
    </tr>
  </thead>
  <tbody>

You can obviously ignore first ten lines since you only care about the submissions.
Next for all submissions, they should begin with <tr> in single line, and end with </tr> in single line. For every  <tr> .... </tr> , there're four lines inside it, each line contains one <th> .... </th>. The html tag of <th> .... </th> contains the information that you want, which is Submit Time, User, Problem, Status in order from top to bottom.

<tr>
<td>    00:22 </td>
        <td>4        </td>
<td>  A</td>
             <td>   Wrong Answer    </td>
      </tr>

2.

<tr>
<td>00:22</td>
<td>4</td>
<td>A</td>
<td>Accepted</td>
</tr>

The input ends when there's two line containing the following tags. Of course, it may have more/less spaces or even no space infront/behind the html tag.

   </tbody>
</table>

The information of the submission contains four things:

1. Submit Time
   The format of the submit time is like the 24-hour clock such as 11:39, 00:45, 02:16. But it represents how many times after the contest starts. For instance, 11:39 means it's 11 hours and 39 minutes after the contest start, 00:45 means it's 45 minutes after the contest start.  The contest is last for one day, so the possible submit time is from 00:00 to 23:59.
2. User
   It is the ID of the user who submits this submission, ID is an integer in range of 0 ~ 100000.
3. Problem
   It's the problem that the submission is submitted to, and it's represented by an uppercase alphabet from A to J. That is, there's 10 problems to submit.
4. Status
   There's only two types of status. Guarantee that there's only one space between "Wrong" and "Answer".
   1. Accepted
   2. Wrong Answer

If we show the sample input in the browser, it may look like the following picture.

Guarantee that there's at most 100 characters in each line and the number of submissions is at least one and at most 200000.
The submit time of the input HTML table is ascending from top to bottom.

Output

Output the scoreboard that generated from the input html table.
You should output N lines, N is the number of user that have at least one submission.
Each line is the score distribution of each user.
The user that got Accepted on more problems should output first. If two user have the same number of problems that they got Accepted, output the the user with less total penalty first. If two user still have the same total penalty, output the user with less user ID first.
The penalty of a single problem is: 

20 × (the number he'd tried before he first get Accepted) + the submit time of the first Accepted submission (Turn into minutes).

And the total penalty is the sum of the penalty of every problem that the user get Accepted. That is, if he'd submitted to the problem, but eventually didn't get Accepted, don't count the penalty of it to the total penalty.

For each line output the follwing information seperated by space.
First output the user id, and then x/y of all the ten problems from A to J.
x := Total times that the user submit to this problem until his first AC submission(include the first AC submission). If the user hasn't submitted to this problem, replace it by "-".
y := The penalty of the problem. If the user hasn't got Accepted on this problem, replace it by "-".
Lastly, output the number of problem that the user get Accpeted and the total penalty.
Be aware that the user may submit to the problem after he/she had already get Accpeted.

Sample Input  Download

Sample Output  Download

Tags

Discuss