CSES 2189 ↗

Point Location Test

Whether `p₃` lies left of, right of, or on the directed line from `p₁` to `p₂`.

1
submissions
1.000
best score

There is a line that goes through the points p1=(x1,y1) and p2=(x2,y2). There is also a point p3=(x3,y3).

Your task is to determine whether p3 is located on the left or right side of the line or if it touches the line when we are looking from p1 to p2.

Input

The first input line has an integer t: the number of tests.

After this, there are t lines that describe the tests. Each line has six integers: x1, y1, x2, y2, x3 and y3.

Output

For each test, print "LEFT", "RIGHT" or "TOUCH".

Constraints

  • 1≤t≤105
  • −109≤x1,y1,x2,y2,x3,y3≤109
  • x1≠x2 or y1≠y2

Example

Input:

3
1 1 5 3 2 3
1 1 5 3 4 1
1 1 5 3 3 2

Output:

LEFT
RIGHT
TOUCH

Statement © the CSES Problem Set. View the original

The specification is at TalosEval/Problems/CSES/PointLocationTest/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
570,349,748570,349,748

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

Results

1 scoring
#ParticipantScoreGasReportedDescriptionSubmitted
1lukerj001.000570,349,748talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-25 13:44 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.