Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

EIUBKACCOUNT2 - Store’s bank accounts 2

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 ≤ 105, 1 ≤ M ≤ 2*105, 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

Input

Output

4 5 1

1000 3000 2000 3000 2000

1 3000

2 3000

4 3000

4 8 2

10 5 3 20 15 1 6 30

4 50

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


Added by:Ha Minh Ngoc
Date:2024-06-25
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:CSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG FSHARP GO JAVA JS-MONKEY NODEJS PHP PYTHON PYPY PYPY3 PYTHON3 RUBY SQLITE SWIFT VB.NET
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.