In the Splitwise app, people form groups and add the expenses of members of the group. This is especially useful for vacations, where people traveling in a group can maintain an account of their expenses and who paid the bills.

All people in the group are assigned distinct IDs between 1 and N, where N is the size of the group.

In addition to keeping a record of the expenditure, Splitwise also calculates the list of shortest-path transfers (defined later) that will settle up all dues.

Each transaction has the following parameters:-

transaction_id - It is a string representing the unique ID by which the transaction is identified.
paid_by - It is a list of lists, where each element of the list is another list having the form [x, y]. Here, x and y denote that person having ID x paid Rs. y.
split_as - It is a list of lists, where each element of the list is another list having the form [x, y]. Here, x and y denote that after all dues are settled, a person having ID x will ultimately contribute Rs. y to the transaction.

For any given transaction, the following condition holds true:-

\(Total\_amount\_paid = Sum\_of\_all\_splits\)

In other words, the sum total of all amounts in list paid_by equals the sum total of all amounts in list split_as.

Following is the example of a transaction in a group of size N=64:-

transaction_id : "#f1230"
paid_by : [ [1, 30], [4, 100], [63, 320] ]
split_as : [ [1, 120], [2, 20], [3, 40], [4, 40], [37, 100], [51, 40], [53, 90] ]

Shortest-Path Transfers: Shortest-path transfers lead to a reduction in the number of transfers.

Specifically, for a group having multiple transactions, the shortest-path transfers will be a list of payments to be made such that:-

Each payment can be represented by a list of the following form:- [payer_id, payee_id, amount]. There is only 1 payer, and 1 payee in each payment, which are distinct from each other. So, \(payer\_id \neq payee\_id\), for any payment.
Each person (out of the N people) can only either be the payer (in all payments involving him), or the payee, but not both.
The total amount of money that each person should receive/spend, must be equal to the total amount he would receive/spend according to the given list of transactions.

Clearly, there can be several shortest-path transfers for a particular list of transactions.

Specifically, the lexicographically smallest shortest path has the following:-

Arrange people who have borrowed money in ascending order of their IDs. Do the same for people who have lent money.
Now, construct payments so that the least borrower ID has to pay the least lender ID. Continue this process, till all debts have been settled.

Task

Given N members in a group, and lists representing the transactions(expenses), print the payments involved in the lexicographically smallest shortest-path transfers for the group.

Example

Input:

N = 4
5 transactions, that can be represented as follows:-
- transaction_id = "#a1234", paid_by = [ [1, 60] ], split_as = [ [2, 60] ].
- transaction_id = "#a2142", paid_by = [ [2, 40] ], split_as = [ [3, 40] ].
- transaction_id = "#b3310", paid_by = [ [3, 30] ], split_as = [ [4, 30] ].
- transaction_id = "#b2211", paid_by = [ [4, 30] ], split_as = [ [3, 30] ].
- transaction_id = "#f1210", paid_by = [ [3, 20] ], split_as = [ [1, 20] ].

Output:

2 payments (of the form [payer_id, payee_id, amount]) are to be made, represented by the list:-
- [ [1, 2, 20], [1, 3, 20] ]

Approach:

The given list of payments satisfies all three necessary conditions. Hence, it is a Shortest-Path Transfer.

Function description

Complete the function solve provided in the editor. This function takes the following 2 parameters and returns the required answer:

N: An integer, representing the number of people in the group.
transaction_list: A list (vector) of transactions. Each transaction is a dictionary, having keys “transaction_id”, “paid_by” and “split_as”. (The contents of each transaction are explained above)

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

The first line contains two space-separated integers N and M, the number of people in the group, and the number of transactions recorded.
The next lines describe the M transactions as follows:-
- Each new transaction begins from a new line.
- The first line of each transaction contains a string, representing the transaction_id of the transaction.
- The 2nd line of each transaction contains 2 space-separated integers n_payers and n_splits.
  n_payers denotes the number of people in the paid_by list. n_splits denotes the number of people in the split_as list.
- The next n_payers lines contain two space-separated integers, the payer and the amount paid.
- The next n_splits lines contain two space-separated integers, the borrower and the amount borrowed.

Output format

Print the answer in the given format.

In the first line, print a single integer K, denoting the number of payments involved in the Shortest Path Transfer.
The next K lines should represent the K payments. Each payment should be printed in a single line as 3 space-separated integers payer_id, payee_id, and amount. Here, payer_id is the ID of the person who needs to pay the amount of money to the person with ID payee_id.

Constraints

\(2 \leq N \leq 2*10^{5}\)
\(1 \leq M \leq 5000\)
\(1 \leq len(transaction[i][paid\_by]) + len(transaction[i][split\_as])\leq 50\)
\(1 \leq total\_money\_exchanged\_in\_each\_transaction \leq 10^{7}\)