Reconcile the Books

At the end of the month an accountant matches the company's ledger against the bank's statement. Each ledger entry and each bank line is an (id, day, amount) tuple: id is a string, day is the day number in the accounting period (1, 2, 3, ...) and amount is a whole number of cents. The bank often records a payment a few days before or after the ledger does, so the days do not have to agree exactly.

Match them with this rule. Go through ledger in order. For each entry, look at the bank lines that are not matched yet, have exactly the same amount, and are at most window days away (abs(bank_day - ledger_day) <= window). If there are any, match the entry with the one closest in days; if several are equally close, with the one that comes first in bank. If there are none, the entry stays unmatched.

Write reconcile(ledger, bank, window) that returns a tuple of three lists: the matches as (ledger_id, bank_id) tuples in ledger order, the ids of the unmatched ledger entries in ledger order, and the ids of the unmatched bank lines in bank order.

Examples

ledger = [('L1', 3, 1500), ('L2', 5, 990), ('L3', 9, 1500), ('L4', 12, 700)]
bank = [('B1', 4, 1500), ('B2', 2, 1500), ('B3', 6, 990), ('B4', 20, 700), ('B5', 8, 1500)]
reconcile(ledger, bank, 3)
# returns ([('L1', 'B1'), ('L2', 'B3'), ('L3', 'B5')], ['L4'], ['B2', 'B4'])

L1 (day 3) could take B1 (day 4) or B2 (day 2), both one day away, so it takes B1, which comes first in bank. The only bank line with L4's amount is 8 days away.

Constraints

• Up to 20,000 ledger entries and 20,000 bank lines; ids are different within each list.
• 0 <= window <= 31, days from 1 to 400, amounts from 1 to 10,000,000.