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 criteria should be taken into account as below:

• If two accounts have the same balance, the account which has fewer number of transactions will be chosen for the next transaction.
• If two accounts have the same balance and number of transactions, the account with smaller ID will be chosen for the next transaction.
• After a successful transaction, an account has to wait for 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 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 ≤ K < N ≤ 10^5, 1 ≤ M ≤ 2\times10^5)~ .
• The second line contains ~M~ integers, each representing an amount that the store will receive.

Output

• For each account, output the account number and total transaction amount. The list should be sorted in descending order of total transaction amount and account's ID.

Sample Input 1

4 5 1
1000 3000 2000 500 3000

Sample Output 1

1 4000
2 3000
3 2000
4 500

Sample Input 2

4 8 2
10 5 3 20 15 1 6 30

Sample Output 2

4 50
2 20
1 16
3 4

Note:

• There are ~50\%~ of testcases that have ~K = 1, N ≤ 100~.