A store manages N customers identified from 0 to N-1. Each customer can place multiple orders, where each order includes a product name, a price, and a quantity. Orders are processed based on priority: orders with higher prices are handled first, and if two orders have the same price, the one with smaller quantity is handled first.

The system keeps track of each customer's activity over time. The total spending is the total money the customer has spent, calculated by adding up all values of price × quantity. Each order also gives reward points, which are equal to one-tenth of its value (rounded down to units). A customer's score is calculated by adding the total spending and three times the total reward, so customers who earn more rewards are considered more valuable.

The system supports adding new orders, removing the highest-priority order of a customer, and finding the top K customers. Customers are ranked by score in decreasing order; if two customers have the same score, the one with higher spending comes first, and if they are still equal, the customer with the smaller ID comes first. If multiple customers have the same score as the K-th customer, all of them must be included in the result.

Input

The first line contains two positive integers N, the number of customers, K, and Q, the number of operations, respectively (0 < K ≤ N ≤ ~10^{6}~, 0 < Q ≤ ~10^{5}~).

Each of the next Q lines describes an operation in one of the following forms:

• + customer_id item_name price quantity: add a new order
• - customer_id: remove the highest-priority order

Note: All integers do not exceed ~10^{9}~.

Output

Print the list of customers including customers'IDs, score, total spending and total reward. The list is ranked in descending order based on their scores. If multiple customers have the same score as the K-th ranked customer, all of them must be included in the output.

Example 1

Input

3 2 3
+ 1 laptop 1000 2
+ 0 laptop 1000 2
+ 2 laptop 1000 2

Output

0 2600 2000 200
1 2600 2000 200
2 2600 2000 200

Example 2

Input

2 1 3
+ 0 laptop 1000 2
+ 1 phone 800 1
- 0

Output

1 1040 800 80