Description

Price of fertilizers in the world are raising! Adding Jinkela in fertilizer, one bag can cover two bags!!

Although Jinkela has been sold for over 10 years, people from America, Africa, Japan are still lining up in a queue to buy it. Each person is given a unique id x. The country of each person can be identified by the remainder of his id divided by 3. If x mod 3 = 0, he is from America; if x mod 3 = 1, he is from Africa; if x mod 3=2, he is from Japan.

Lining up is tedious, everyone wants to cut in line! These American, African, and Japanese follow some rule when they cut in line:

When a person enters the queue,

1. If the queue is empty, he becomes the first person in the queue.
2. If there isn't anyone who comes from the same country in the queue, he becomes the last person in the queue.
3. Otherwise, of all people coming from the same country in the queue, he finds the last of them and lines up after him ( and possibly cuts in line ).

As old saying goes, "all humans are equal, but some humans are more equal than others." People with id of multiples of five are VIP. VIP enter another special queue instead of the normal one. All VIP are polite and highly educated, so they don't cut in the line.

Every time the supplier provides Jinkela with first person from both normal queue and VIP queue. After a person buys Jinkela, he leaves the queue immediately and will not enter the queue again.

You are curious about the order people get their Jinkela. Given the status of the queue. Whenever someone leaves the queue, output his id. If two people leave at once, output VIP id first and then the normal id.

Refer to the sample IO for example if you don't understand the rule.

For example, assume the queue is empty initially

• ENQUEUE 0: An American with id 0 enters the VIP queue.

queue:
VIP queue: 0

• ENQUEUE 1: An African with id 1 enters the queue. Since the queue is empty, he becomes the first person in the queue.

queue: 1
VIP queue: 0

• ENQUEUE 3: An American with id 3 enters the queue. Since there isn't any other American in the queue, he becomes the last person in the queue.

queue: 1 3
VIP queue: 0

• ENQUEUE 4: An African with id 4 enters the line. Since he finds an African (id=1) in the line, he lines up right after him.

queue: 1 4 3
VIP queue: 0

• ENQUEUE 7: An African with id 7 enters the line. He finds two African (id=1, id=4) in the line, where African with id 4 is the last one, he lines up after American with id 4.

queue: 1 4 7 3
VIP queue: 0

• ENQUEUE 10: An African with id 10 enters the VIP queue.

queue: 1 4 7 3
VIP queue: 0 10

• ENQUEUE 30: An American with id 30 enters the VIP queue. He says hi to American with id 0 but does not try to cut in line.

queue: 1 4 7 3
VIP queue: 0 10 30

• DEQUEUE: The first person of both queue leaves the line. Output VIP id(0) first and then normal id(1).

queue: 4 7 3
VIP queue: 10 30
output:“0 1”

• DEQUEUE: The first person of both queue leaves the line. Output VIP id(10) first and then normal id(4).

queue: 7 3
VIP queue: 30
output:“10 4”

• DEQUEUE: The first person of both queue leaves the line. Output VIP id(30) first and then normal id(7).

queue: 3
VIP queue:
output:“30 7”

• DEQUEUE: The first person of the normal queue leaves the line. Output normal id(3).

queue:
VIP queue:
output:“3”

Note

It is highly recommended to use IO optimization to avoid TLE in this problem.
Before submitting your answer to OJ, add these two lines of codes in the beginning of the main function.

We promise that if both queues are empty, no DEQUEUE will happen.

Input

Each line contains one instruction only.

• ENQUEUE x: person with id x enters the queue. x is an integer. 0<=x<=9*10^8
• DEQUEUE: the first person in both normal queue and VIP queue buy their Jinkela and leave the queue.

Please keep reading input until reach EOF.

For the first 3 testcases, the number of instructions ≤ 1000.

For the rest of the testcases, the number the number of instructions ≤ 1100000.

Output

For each DEQUEUE command, please output all ids who leave the queue.
Each output occupies a single line with a '\n' at the end of the line.
If two people are leaving at once, output the VIP id first and then the normal id, and seperate them with a single space.
Don’t output a space at the end of the line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A Co-Sequence is a sequence which consists of 8 integers.

And you can execute three types of operations on a Co-Sequence:

1. cyclically shift all the integers to the right in Co-Sequence by one unit
2. exchange the position of arbitrary two adjacent integers in Co-Sequence
3. sort some consecutive integers in increasing order in Co-Sequence. Specially, you can execute this type of operation on a Co-Sequence at most once

Now you are given two Co-Sequence  and . You need to answer the minimum number of operations you need to execute on  to make  be as same as . Note it may be impossible to make  be as same as .

You need to solve  tasks.

Input

The first line contains an integer  – the number of tasks you need to solve.

The first line of each task contains 8 integers – the 8 integers of .

The second line of each task contains 8 integers – the 8 integers of  .

All the integers in Co-Sequence must be non-negative and be less than or equal to .

It's guaranteed that:

• The 1st testcase must be identical to the Sample #1 below
• For the first 2 testcase: only the first type operation is necessary
• For the first 4 testcase: only the first and the second type operations are necessary
• For the first 5 testcase: if the third type operations is necessary, then you must execute the third type operation to sort the whole sequence

Output

For each task, output the minimum number of operations you need to execute on  to make  is as same as .

If it's impossible to make  be as same as , output -1 instead.

Note: there are two sample below. "# Sample Input 1/2/3" and "# Sample Output 1/2/3" are not the part of input and output.

They are just for marking that the following content corresponds to which sample.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

DuckDuck are a lazy vendor. To keep up with the trend of AI, he wants to write a program to handle the stall automatically. Can you help him?
The commodity (商品) has weight and price. Initially there're some commodities (the left over from yesterday). The program has to handle four types of event.

Input

The first line contains a single integer N (N <= 100000) representing the number of commodity you initially own. The next N lines each contain two integers representing the weight and price weight and price of each commodity.
Next line contains a single integer Q (Q <= 100000) representing the number of events. The next Q lines representing the information of each events.
For each events, first contains an integer representing the type of the event.
If the type is 1 or 2, then there will be two integers follow, representing the weight and price respectively.
If the type is 3 or 4, then there will be one integer follows, representing the weight or price depending on the type of events).
Guarantee that (1 <= all the weight and price <= 1000000)

Constraint of testcases:

Testcase 1 ~ 2: N, Q <= 2000, event type = {1, 2, 3}, commodity in your stall are all unique.
Testcase 2 ~ 4: Event type = {1, 2, 3}, commodity in your stall are all unique.
Testcaes 5: Commodity in your stall are all unique.
Testcaes 6: Event type = {1, 2, 3}
Testcaes 7 ~ 8: No other constraint.
 

Output

For event type 2, if you sell the customer output "OK", otherwise output "No Item".
For event type 3 and 4, if you sell the customer please output "OK" and the weight and price of the commodity that you sell seperated by space, otherwise output "No Item"
Remember to add a newline character at the end of the output of each event.
 

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

set:

Sets are containers that store unique elements following a specific order.

#include <set>

begin: Return iterator to beginning

end: Return iterator to end

rbegin: Return reverse iterator to reverse beginning

rend: Return reverse iterator to reverse end

empty: Test whether container is empty

clear: Clear content

size: Return container size

insert: Insert element

erase: Erase elements

find: Get iterator to element

lower_bound(val): Return an iterator pointing to the first element in the container which is not considered to go before val (i.e., either it's equivalent or goes after).

list:

Lists are sequence containers that allow constant time insert and erase operations anywhere within the sequence, and iteration in both directions.

#include <list>

begin: Return iterator to beginning

end: Return iterator to end

rbegin: Return reverse iterator to reverse beginning

rend: Return reverse iterator to reverse end

empty: Test whether container is empty

clear: Clear content

size: Return container size

front: Access first element

back: Access last element

emplace_front: Construct and insert element at beginning

emplace_back: Construct and insert element at the end

push_front: Insert element at beginning

push_back: Insert element at the end

pop_front: Delete first element 

pop_back: Delete last element

erase: Erase elements

remove: Remove elements with specific value

vector:

Vectors are sequence containers representing arrays that can change in size.

#include <vector>

begin: Return iterator to beginning

end: Return iterator to end

rbegin: Return reverse iterator to reverse beginning

rend: Return reverse iterator to reverse end

empty: Test whether container is empty

clear: Clear content

size: Return container size

front: Access first element

back: Access last element

emplace_back: Construct and insert element at the end

push_back: Add element at the end

pop_back: Delete last element

queue:

#include <queue>

empty: Test whether container is empty

size: Return container size

push: Insert element

pop: Remove next element

front: Access next element

priority_queue:

#include <queue>

empty: Test whether container is empty

size: Return container size

push: Insert element

pop: Remove top element

top: Access top element

stack:

#include <stack>

empty: Test whether container is empty

size: Return container size

top: Access next element

push: Insert element

pop: Remove top element

map:

#include <map>

begin: Return iterator to beginning

end: Return iterator to end

rbegin: Return reverse iterator to reverse beginning

rend: Return reverse iterator to reverse end

empty: Test whether container is empty

clear: Clear content

insert: Insert Element

erase: Erase element

count : Count elements with a specific key

find: Get iterator to element

operator[]: Access element

deque:

#include <deque>

push_front: Insert element at beginning

push_back: Insert element at the end

pop_front: Delete first element 

pop_back: Delete last element

empty: Test whether container is empty

size: Return container size

insert: Insert element

erase: Erase element

operator []: Access element

front: Access first element

back: Access last element

clear: Clear the container

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss