Problem

Given two jug capacities a and b, and a target amount target, return the shortest sequence of operations needed to measure exactly target gallons. A state is represented as (x, y), where x and y are the current amounts in the two jugs. Allowed operations are: fill either jug, empty either jug, or pour from one jug into the other until the source is empty or the destination is full. Return the list of states from (0, 0) to a state containing exactly target, or an empty list if it is impossible.

Examples

Example 1:

Input: a = 3, b = 5, target = 4
Output: [[0,0],[0,5],[3,2],[0,2],[2,0],[2,5],[3,4]]
Explanation: The final state contains exactly 4 gallons in the 5-gallon jug.

Example 2:

Input: a = 2, b = 6, target = 5
Output: []
Explanation: It is impossible to measure 5 gallons using jugs of size 2 and 6.

Constraints

• 1 <= a, b <= 100
• 0 <= target <= max(a, b)
• Each operation must produce a valid jug state
• Return any one shortest valid sequence