405091: GYM101790 A Pizza Universe

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A. Pizza Universetime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

N Ricks from different universes gathered in a restaurant to celebrate Rick's Birthday. The restaurant accepts only pizzcoins in cash, but some of the Ricks had no enough cash to pay.

More precisely, i-th Rick ordered food for Ai pizzcoins, paid Bi pizzcoins in cash, and together they paid exactly the amount of the check.

After the party Ricks want to pay off each other. Every Rick has infinite amount of pizzcoins in his bank account and may transfer pizzcoins to the others Ricks.

Find any list of transfers satisfying following conditions:

  • no one owes pizzcoins in the end. That is, after paying the check in the restaurant and all transfers, every Rick spent exactly what he spent in the restaurant;

  • the number of transfers doesn't exceed N;

  • the total amount of transfered pizzcoins doesn't exceed doubled check amount.

Input

The first line contains one integer N (2 ≤ N ≤ 1000), denoting the number of Ricks.

The second line contains N integers Ai (0 ≤ Ai ≤ 106), denoting the price of food in pizzcoins ordered by i-th Rick.

The third line contains N integers Bi (0 ≤ Bi ≤ 106), denoting the amount of pizzcoins were paid by i-th Rick in cash.

It is guaranteed that .

Output

Display the list of pizzcoin transfers. Every transfer should be displayed in a seperate line, and should contains the following format: "F T S", where F is a number of Rick who makes transfer, T is a number of Rick who receives pizzcoins, S is the number of transfered pizzcoins (1 ≤ F, T ≤ N; 0 ≤ S ≤ 2 × 109).

It is guaranteed that the list will contain at least one item. You can choose any solution that satisfies the constraints.

ExamplesInput
6
100 200 50 150 400 150
50 500 0 150 100 250
Output
1 2 50
3 2 50
5 2 200
5 6 100
Input
2
0 1000000
1000000 0
Output
2 1 1000000

加入题单

上一题 下一题 算法标签: