Shortfall report: hints, no solution

A supplier's delivery note lists what should arrive as pairs of SKU and quantity, and each SKU appears on the note at most once. The dock then logs what was unloaded, also as pairs of SKU and quantity, but a SKU can appear on several log lines because it comes off different pallets, so its received quantity is the sum of its lines.

Return one pair per short SKU: the SKU and the gap, meaning expected minus received, for every SKU whose received total is below its expected quantity. Sort the pairs by SKU ascending. A SKU that never shows in the log has received zero, and a SKU that was received but is not on the note is ignored. Return an empty list when nothing is short.

Examples

Input

expected = [[10, 5], [20, 3], [30, 4]], received = [[10, 5], [20, 1], [30, 1], [30, 1]]

Output

[[20, 2], [30, 2]]

Note

SKU 20 got 1 of 3 and SKU 30 got 1 plus 1 of 4, so both are short by 2.

Input

expected = [[1, 2]], received = [[1, 3]]

Output

[]

Note

Received exceeds expected, so nothing is short.

Input

expected = [[5, 4], [2, 6]], received = [[9, 10]]

Output

[[2, 6], [5, 4]]

Note

SKUs 2 and 5 never arrived, SKU 9 is not on the note and is ignored, and the pairs are sorted by SKU.

Constraints

• 0 <= expected.length <= 50000 and 0 <= received.length <= 80000
• Each pair is [sku, quantity] with 1 <= sku <= 2000000
• 1 <= quantity <= 10000 per line
• Return pairs sorted by SKU ascending

Hint 1: a nudge

For one SKU on the note, what exactly do you need to know about the log to decide if it is short?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing