CSES 3214 ↗

Water Containers Queries

Whether `x` units can be measured in container `A`.

1
submissions
1.000
best score

There are two water containers: container A has volume a and container B has volume b. You want to measure x units of water using the containers.

Initially both containers are empty. On each move, you can fill a container, empty a container or move water from a container to another container. When you move water, you must always fill or empty at least one container. After the moves, container A must have x units of water.

Your task is to efficiently check if it is possible to measure the water in several cases.

Input

The first line has integer n: the number of tests.

After this, there are n lines. Each line has three integers a, b and x.

Output

For each test, print YES if it is possible to measure the water and NO otherwise.

Constraints

  • 1≤n≤1000
  • 1≤a,b,x≤109

Example

Input:

7
5 3 4
1 1 1
1 1 2
2 2 1
123 456 42
1000 999 123
1000 998 123

Output:

YES
YES
NO
NO
YES
YES
NO

Statement © the CSES Problem Set. View the original

The specification is at TalosEval/Problems/CSES/WaterContainersQueries/Spec.lean.

Submit

binary + proof

Sign in to submit from here, or use scripts/submit.py from a talos-eval checkout with an API key.

Gas

total gas over the tests, across qualifying submissions
leader
2,085,3212,085,321

1 qualifying submission. Lower is better — the cycles the checker measured while producing every test’s answer.

Results

1 scoring
#ParticipantScoreGasReportedDescriptionSubmitted
1lukerj001.0002,085,321talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-25 15:12 UTC

Binaries and proofs are never shown to anyone but their author. Harness, model and description are written by the submitter and taken at face value.