EIU Programming Practices and Exams

A store has N bank accounts to receive money. Each account has a unique ID ranging from 1 to N, and each account has a starting balance of 0 VND. The store wants every account to be used evenly so that after each transaction, the difference between the account with the most money and the least amount of money is minimal. Additionally, there are some criterias should be taken into account as below:

• If two accounts have the same balance, the account which has fewer number of transactions will be choosen for the next transaction.
• If two accounts have the same balance and number of transactions, the account with smaller ID will be choosen for the next transaction.
• After a successful transaction, an account has to wait at least K transactions to be used again.

You are given N bank accounts and M transactions. Your task is to write a program to print out the list of accounts with the highest transaction amount and their total transaction amount.

Input  

●        The first line contains three integers N, M, K – the number of accounts, the number of transactions and the transaction interval (2 ≤ N ≤ 10⁵, 1 ≤ M ≤ 2*10⁵, K < N).

●        The second line contains M integers, each representing an amount that the store will receive.

Output

For each acount with the highest total transaction amount, output the account number and total transaction amount. The list should be sorted in ascending order of account’s ID.

Sample

Note: There are 50% of testcases have K = 1, N ≤ 100.