Description

Notice: Please use C++11 or above to submit this problem!

After watching the movie 21, Kuo is curious about casino.

There is a casino which opens N days in this month.

There will be two kind of events in a day.

1. Guest <Someone> <Money> <Skill>. It means <Someone> enter the casino with <Money> money. <Someone> are their names, <Money> is the amount of money with them, and <Skill> is how well they play. If <Someone> are already in the casino or are blacklisted, ignore this event.
2. Win <Someone> <Money>. It means <Someone> win <Money> money in a play from the casino. <Money> may be positive or negative. If <Someone> are not in the casino or are blacklisted, ignore this event.

Whenever someone enter the casino, they have to pay T entrance fee to the casino. The enterance fee may change every day.

Whenever one become bankrupt, they will be kicked out of the casino and be blacklisted.

If the amout of money someone win in a play exceed (that is, >) twice of their <Skill>, they will be seen as cheaters, kicked out of the casino, and blacklisted. (The casino still has to pay the money they win to them.)

Someone blacklisted are not permitted to enter the casino. In particular, when someone blacklisted wants to enter the casino, they won't be charged the enterance fee.

Note: If someone have to pay X money but they only have Y money where Y <= X, they will only pay Y money and become bankrupt.

At the end of each day, everyone will leave the casino.

Please help Kuo-chan find how much income the casino gets in this month and who are blacklisted.

Input

The first line of the input contains a number N — the number of days in this month.

The following contains N blocks.

The first line of each block is Casino Q T — it means there will be Q events and the entrance fee is T this day.

The next Q lines is one of the following:

1. Guest <Someone> <Money> <Skill>
2. Win <Someone> <Money>

N <= 1000, Q <= 100. 

There will be at most 1000 different people come to the casino; that is, there are at most 1000 people with different names. Therefore, there will be at most 1000 people blacklisted.

All number is within the range of int.

Output

You should print a number U in the first line — how much income the casino gets in this month.

If there are K people blacklisted in this month, you should output their names in K lines in the order they get blacklisted.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

Kuo-chan is given a sequence A and a constant K as his birthday present from Yang-chan.

Kuo-chan is allowed to perfrom the following operation:

1. push x — push x to the tail of A
2. pop — remove the median value of A （the median value of A is A[ (|A|+1)/2 ], with index start at 1）
3. programming tanoshi — for every element a in A, assign a % K to a
4. reverse — reverse the whole A, the head becomes the tail and the tail becomes the head

Whenever performing pop operation, the length of A is guaranteed to be odd, hence A won't be empty.

For example, if A = [4, 3, 5], K = 2

push 11　►　A = [4, 3, 5, 11]

reverse ► A = [11, 5, 3, 4]

push 7　►　A = [11, 5, 3, 4, 7]

pop　►　A = [11, 5, 4, 7]

programming tanoshi　►　A = [1, 1, 0, 1] 

Yang-chan is curious about what A is after Kuo-chan performs some operations to it.

Help him find it out!

（Remember to include function.h in your function.cpp file.）

Input

The first line contains three integers N K Q — the length of A, the constant Yang-chan gives Kuo-chan, the number of operations Kuo-chan performs.

The second line contains N integers a₁, a₂, ..., a_N （1 <= a_i <= N） — the elements of A. 

Each of the next Q lines describes the operations. Each line is one of three types:

1. push x （1 <= x <= 10000）
2. pop
3. programming tanoshi
4. reverse

Different testcases have different constraints.

1. N <= 10³, Q <= 2N, K <= 4000, operations: {pop, push}
2. N <= 10³, Q <= 2N, K <= 4000, operations: {pop, push, programming tanoshi}
3. N <= 10⁵, Q <= 2N, K <= 4000, operations: {pop, push}
4. N <= 10⁵, Q <= 2N, K <= 4000, operations: {pop, push, programming tanoshi}
5. N <= 10⁵, Q <= 3N, K <= 4000, operations: {pop, push, programming tanoshi, reverse}
6. N <= 10⁵, Q <= 3N, K <= 4000, operations: {pop, push, programming tanoshi, reverse}

Output

You should print one line containing the elements of A after the operations. For 1 <= i <= |A|, the i-th number should be A[ i ].

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

The Traveling Salesman Problem (TSP) is a classical problem that we are to find the shortest distance traversing all vertices in a graph from any source and returning to the source, which is considered hard for computers (and maybe human as well).

Nevertheless, the TSP on tree is quite easy: the shortest circuit must visit all edges exactly twice. You could prove this by induction. So let's consider the Open Loop TSP, in which the salesman is not required to return to the source. 

In this problem, your task is the Open Loop TSP on trees, i.e., finding the shortest distance traversing all nodes in a tree from any source without returning to the source.

Input

There's an interger \(n\) in the first line, indicating the number of nodes in the tree.

The next \(n-1\) lines consist of three integers \(a_i,b_i,w_i\) representing that there's an bidirected edge between \(a_i\) and \(b_i\) weighing \(w_i<2^{31}\).

For \(50\%\) of the testcases, \(n\leq5\times10^4\). For the other \(50\%\) of the testcases, \(n\leq10^6\).

Output

Please print the shortest distance traversing all nodes in a tree from any source without returning to the source.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Procat (破貓) has a lot of electrical appliances in his dormitory, such as computer, refrigerator, and electric fan. He wants to connect all the appliances to the power outlet. There is only one power outlet in his dormitory, so he needs to use extension cords and power strips to connect all the appliances to the power outlet.

Extension cords and power strips Procat currently using don't have overcurrent protection. As a friend of Procat, you are very concerned about electrical safety. You want to help Procat to connect all the appliances to the power outlet in a safe way. Luckily, you have some spare power strips with overcurrent protection. But you don't have any spare extension cords.

Power strips you have got one input and two outputs. Power strips can connect to extension cords, but power strips cannot directly connected to each other.

The price of the high-quality extension cord you want to buy is proportional to the current flowing through it. You wants to minimize the total price of the extension cords you needs to buy.

Calculate total price of the extension cords you need to connect all the appliances to the power outlet.

• After connecting all the appliances to the power outlet, it should look like a binary tree. The power outlet is the root of the tree, and the appliances are the leaves of the tree. The power strips are the internal nodes of the tree. The extension cords are the edges of the tree.

Sample

Following figures show examples of optimal ways to connect the appliances to the power outlet in each sample testcase. In each figure, squares represent power strips, circles represent appliances, and edges represent extension cords. The total price of the extension cords is the sum of current flowing through all the edges.

Sample testcase 1:

Sample testcase 2:

• Hint: Huffman Coding

Input

First line contains an integer \(N\), the number of electrical appliances Procat wants to connect to the power outlet.

The second line contains \(N\) integers \(a_1, a_2, \dots, a_N\), the power consumption of the \(N\) electrical appliances.

\(N\)
\(a_1 \quad a_2 \quad \dots \quad a_N\)

Constraints

• \(1 \leq N \leq 10^4\)
• \(1 \leq a_i \leq 10^9\)

Output

Output contains one line, the minimum total price of the extension cords Procat needs to buy. You don't need to output a newline at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You signed up for an escape room experience, but something feels off.

The facility has $N$ rooms, numbered $1$ through $N$. Each room has a single door that leads to exactly one other room — or directly outside. You start from room $1$ and follow the doors one by one.

Twenty minutes in, your partner grabs your arm. "We've walked through this room before."

She's right. Somewhere in the layout, an exit circles back. If that loop exists, you're going to keep walking the same stretch of hallway forever. The first room you step into for the second time is where the loop begins.

Given the exit map, find that room. If the path eventually leads outside, output the number of the last room you pass through before the exit.

Implement the following function:

Node *detectCycle(Node *head);

The Node struct is defined in function.h:

typedef struct Node {
    struct Node *next;
} Node;

head points to room $1$. Return the node where the loop begins, or the last node before the exit if no loop exists.

Hint: Compare pointers directly — do not attempt to store or index nodes by values of any kind. Any solution that allocates auxiliary storage proportional to $N$ will exceed the memory limit on the large test cases.

Input