Description

In this world, everyone needs to work to earn money to survive.

Jobs are provided by armored men (盔甲人), and little cutes (小可愛) will try to get the jobs they want.

After working, the armored men will calculate the day's salary for each little cute.

To efficiently pay salaries to little cutes, the armored men need to track which job is chosen by which little cute. Therefore, they decided to write a program to assist them.

There are N jobs, numbered from 1 to N, and each job has a type t_i (1 ≤ i ≤ N).

Next, there will be Q events happening. Each event will have an Action and an ID. The Action can only be one of two types: {"Apply", "Quit"}. The ID represents the identification number of the little cute in the event. "Apply" means that the little cute with the specified ID wants to apply for the jobs, while "Quit" means that the little cute with the specified ID wants to quit from his jobs.

For an event where the Action is "Apply", there will be two lines of input:

• The first line contains K and Order, indicating that the little cute wants to apply for K jobs, and Order specifies the order in which the little cute prefers jobs of the same job type. The job_id (1 ≤ job_id ≤ N) should conform to the specified Order.
• The second line contains K positive integers, representing the K jobs that the little cute wants to apply for.

Note: The Order can only be one of three types: {"MIN", "MAX", "MID"}. When Order is "MIN", the little cute prefers the job with the smallest job_id. When Order is "MAX", the little cute prefers the job with the largest job_id. When Order is "MID", the little cute prefers the job with the "median" job_id.

Assuming there are J sorted job_id's, the median is defined as:

• If J is odd, the median is the job_id at the (J - 1) / 2 position.
• If J is even, the median is the job_id at the (J / 2) - 1 position.

For example:

• If job_id = {1, 3, 5, 7, 9}, the median is job_id[2] = 5.
• If job_id = {4, 5, 6, 7, 9, 10, 11, 12}, the median is job_id[3] = 7.

And once a little cute gets all his jobs, he will leave the queue; otherwise, he will stay in the queue and cry, and at last the little cute and those behind him all can't get the jobs.

For an event where the Action is "Quit", the little cute with the numbered ID wants to quit from his current jobs. Notice that the jobs he resigns from will not be returned to the armored men (盔甲人), not allowing other little cutes to apply for these jobs.

It is guaranteed that for each little cute, there will be at most one "Apply" and one "Quit" events, and the "Quit" event will always occur after the "Apply" event, meaning that a little cute can only resign after he has applied for jobs.

For each job, you should output the little_cute_id of the little cute who has taken it, or 0 if nobody does (including those returned).

Despite the crying little cute in the queue hindering (阻礙) others from applying for new jobs, little cutes with existing jobs can still take the "Quit" actions. (Please refer to Sample IO 4)

 

Sometimes, when you feel like you can't do it, just give up directly?

  

Constraints

• 1 ≤ N, Q ≤ 2 * 10⁵
• 1 ≤ t_i, ID ≤ 10⁹
• ∑K ≤ 2 * 10⁵

Subtasks

• testcases 1 ~ 3: Action only contains "Apply", Order only contains "MIN", 1 ≤ ID ≤ 10⁶.
• testcases 4 ~ 5: Action contains "Apply" and "Quit", Order contains "MIN" and "MAX".
• testcases 6 ~ 7: No additional constraints.

Input

The first line of input contains two positive integers N, Q, as described in the statement.

Next, there would be N integers, t₁∼ t_N, as the statement describes.

Finally, there would be Q events, each represented by an Action and an ID. The Action can only be one of two types: {"Apply", "Quit"}. The ID represents the identification number of the little cute in the event.

If the Action is "Apply", then you will be given a job set, represented by two lines:

1. the first line contains a positive integer K_ID, denoting the size of the ID_th little cute's job set, and a string Order, specifying the order in which the little cute prefers jobs of the same job type.
2. the second line contains K_ID integers, each denoting one of the job types in this job set.

Output

Output N integers, each integer indicating which little cute has taken the corresponding job.

Please append a space after each number, and add a newline at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss