Problem

At Acme Utilities, you are given two water jugs with capacities jug1 and jug2, and a target amount target. Starting from both jugs empty, return a shortest sequence of valid operations that results in exactly target gallons in either jug.

Valid operations are:

1. Fill a jug completely.
2. Empty a jug completely.
3. Pour water from one jug into the other until the source is empty or the destination is full.

Formal Specification

Implement a function that takes three integers: jug1, jug2, and target. Return a list of states, where each state is [a, b] representing the current amount of water in jug 1 and jug 2. The returned list must start with [0, 0] and end at a state where a == target or b == target. If no solution exists, return an empty list.

Examples

Example 1 Input: jug1 = 3, jug2 = 5, target = 4 Output: [[0,0],[0,5],[3,2],[0,2],[2,0],[2,5],[3,4]] Explanation: The final state has 4 gallons in the 5-gallon jug.

Example 2 Input: jug1 = 2, jug2 = 6, target = 5 Output: [] Explanation: It is impossible to measure exactly 5 gallons with these jug sizes.

Constraints

• 1 <= jug1, jug2 <= 100
• 0 <= target <= max(jug1, jug2)
• Return any one shortest valid sequence if multiple exist.