Description

* 05/28 Update: An underline has been added to a certain sentence *

This is a partial judge problem. 

Built-in Sorting function and C++ containers are forbidden. NO credit if you use any of them. 

---

There are many people buying food at 水木 (shuǐ mù, Water Wood) Food Court every day. The seats are limited, so many students can’t find places to sit during the lunch breaks. If you are a NTHU student, you probably had experienced that before. To know how many seats we need, you must analyze the customer traffic first.

Since the limited seats will influence the number of incoming customers, you might need to create a virtual environment without seating condition. Assume you can cast a spell to remove all furniture and enlarge the ground so that everyone has a space. (They said that programming is like magic in fantasy, so ¯\_(ツ)_/¯)

For simplicity, you only need to look at the traffic of one day in each testcase. Also, everyone eats their food in the food court (they won’t ask for takeout.) In addition, people go to the food court in groups and the people in the same group buy their food from the same store.

In each testcase, there will be n groups and their information will be given in the input one by one. For any group i, the information will be specified in a line consists of 3 integers and 1 string without whitespaces, including:

• The number of people in this group, P_i.
• The time the group arrives at, A_i.
• The time the group leaves at, L_i.
• The name of the store the group shops, S_i

You need to develop a program to organize the data and it should be able to provide the following information that can be queried by a user:

1. The time that the K_th earliest group arrives at.
2. The number of people in the food court at the time T.
3. The time when there are the most people in the food court and the number of the people in the food court at that time. In the case of multiple possible solutions, provide the solution with earliest time of having maximum traffic.
4. A list of the names of all the stores that appeared in the data. The names in the list should be distinct. Print them in the lexicographical order and separate them with a space. Here, the order of the characters is based on the ASCII code. The smaller the code of a character is, the higher priority the character has to be sorted in the front.

Note:

The times people arrive and leave at will be represented by non-negative integers. When group i leaves at time L_i, group i is no longer considered to be in the food court at that time L_i.

If y groups arrive at the same time and x groups have already arrived before that, they will be the x+1_th ~ x+y_th earliest groups. The order inside the y groups is not important. Your program should return same value for the arrival times of the x+1_th ~ x+y_th earliest group, that is, the time when the y groups arrive at.

 

Input

The first line contains an integer n, representing the number of the group today.

The following n lines represent the information about each group. Each of the line consists of:

• 3 integers, P_i, A_i, L_i, representing (1) the number of people (2) the time they arrive (3) the time they leave, separately.
• 1 string without whitespaces, S_i, representing the name of the store where they buy food from.

After those n lines, there will be a line containing only one integer m, representing the number of the queries.

The following m lines represent m queries separately. Each line could consist of one of the following:

1. A string “TIME_ARRIVE” followed by a space and a positive integer K.
2. A string “TRAFFIC_AT” followed by a space and a non-negative integer T.
3. A string “MAX_TRAFFIC”
4. A string “STORE_LIST”

The four types of queries above are corresponding to the four mentioned in the description section.

It’s guaranteed that:

• 1 <= K <= n <= 10^4
• 1 <= m <= 10^2
• 1 <= The number of the available stores <= 1000.

Also, for any group i:

• 1 <= P_i <= 10^8
• 0 <= A_i < L_i <= 10^8
• 1 <= len(S_i) <= 10^2

Output

You need to print the information according to the queries in the input.

1. If the query is “TIME_ARRIVE” and followed by a space and a positive integer K, you need to print an integer that represents the time the K_th earliest group arrives at. Print a newline symbol afterwards.
2. If the query is “TRAFFIC_AT” and followed by a space and a positive integer T, you need to print the number of people in the food court at the time T. Print a newline symbol afterwards.
3. If the query is “MAX_TRAFFIC”, you need to print the time when there are the most people in the food court and the number of the people in the food court at that time. Separate them with a whitespace. Print a newline symbol after the two numbers. In the case of multiple possible solutions, provide the solution with earliest time of having maximum traffic.

1. If the query is “STORE_LIST”, you need to print the names of all the stores that appeared in the data. Print them in lexicographical order and separate them with a space. Print a newline symbol at the end of the line. 

Sample Input  Download

Sample Output  Download

Partial Judge Code

13534.cpp

Partial Judge Header

13534.h

Tags

Discuss