Decision Tree

$N$명의 루노(Runo)들이 2차원 평면 위에서 일을 하고 있다. 오늘 루노들의 일은 두 창고를 오가며 짐을 나르는 것이다.

루노들에게는 $1$번부터 $N$번까지 번호가 붙어있는데, $i$번 루노에게 배정된 두 창고의 위치는 점 $(p\_i, q\_i)$와 점 $(r\_i, s\_i)$이다.

루노들은 효율적인 것을 좋아하기 때문에, 각 루노는 자신에게 배정된 두 창고 사이를 최단경로를 따라 이동한다. 즉, 두 창고를 잇는 선분 위에서만 이동한다.

루노들을 관리하는 아인(AIN)이는 루노 하나의 위치가 주어질 때, 그 루노의 번호를 맞힐 수 있는 결정 트리(Decision tree)를 만들려고 한다.

결정 트리를 간략히 소개하면 다음과 같다.

• 결정 트리는 데이터가 주어질 때 그 데이터에 대해 어떤 의사 결정을 내리는 과정을 트리 형태로 나타낸 것이다.
• 결정 트리에서의 의사 결정은 트리의 루트 노드에서 출발해 어떤 리프 노드(자식이 없는 노드)에 도착할 때까지 계속해서 자식 노드를 따라 내려가는 방식으로 이루어진다.
• 결정 트리의 내부 노드들은 결정 노드(Decision node)라고 부르며, 다음에 방문할 자식 노드를 결정하는 규칙을 담고 있다.
• 결정 트리의 리프 노드들은 종단 노드(Terminal node)라고 부르며, 최종 의사 결정 내용을 담고 있다.

아인이가 만들려는 결정 트리에서 결정 노드와 종단 노드의 정확한 명세는 다음과 같다.

• 결정 노드

  • 내부 인자로 세 정수 $a$, $b$, $c$를 가지며, 왼쪽 자식 노드와 오른쪽 자식 노드를 가지고 있다.
  • 주어진 위치 $(x,y)$에 대해 $ax+by+c$를 계산한다. 그리고 이 값이 양수라면 왼쪽 자식, 음수라면 오른쪽 자식으로 이동한다.
  • 만약, $ax+by+c$의 값이 정확히 $0$이라면 루노의 번호를 맞히지 못한 것으로 판정하고 결정 과정을 마친다.

• 종단 노드

  • 내부 인자로 정수 $i$를 가지며, 자식 노드는 없다.
  • 주어진 위치가 $i$번 루노의 것이라고 판단하고 결정 과정을 마친다.

아인이는 각 루노마다 그에 해당하는 종단 노드를 정확히 하나씩 만들려고 한다. 따라서 아인이가 만드는 결정 트리는 $N$개의 종단 노드와 $N-1$개의 결정 노드, 총 $2N-1$개의 노드를 가지게 된다.

아인이와 함께 정확한 결정 트리를 구성해 보자. 정확한 결정 트리란, 모든 루노에 대해 그 루노가 가질 수 있는 어떤 위치가 주어지더라도 주어진 위치가 그 루노의 것이라고 올바르게 판단할 수 있는 결정 트리를 의미한다.

첫 번째 줄에 일하는 루노의 수 $N$이 주어진다.

다음 $N$개의 줄에는 각 루노에게 배정된 두 창고의 정보가 주어진다. 이 중 $i$번째 줄에는 네 정수 $p\_i, q\_i, r\_i, s\_i$가 주어지며, 이는 $i$번 루노에게 $(p\_i, q\_i)$에 있는 창고와 $(r\_i, s\_i)$에 있는 창고가 배정되었다는 뜻이다.

입력으로 들어온 정보를 따라 정확한 결정 트리를 만들 수 있다면 첫 번째 줄에 Yes를 출력하고, 아니면 No를 출력한다.

Yes를 출력한 경우, 결정 트리를 전위 순회한 순서대로 $2N-1$개의 줄에 노드의 구성을 출력한다.

결정 노드는 ? a b c로 출력해야 하며, $|a|, |b| \leq 10^9, |c| \leq 10^{18}$의 범위를 가지는 정수여야 한다. 주어진 입력에 대해 정확한 결정 트리가 존재한다면 이 제한 안에서 충분히 결정 트리를 구성할 수 있음을 증명할 수 있다.

종단 노드는 ! i로 출력해야 하며, 출력에 $1$ 이상 $N$ 이하의 모든 정수가 $i$로 한 번씩 등장해야 한다.

• $2 \leq N \leq 250$
• $|p\_i|, |q\_i|, |r\_i|, |s\_i| \leq 10^8$
• $(p\_i, q\_i) \neq (r\_i, s\_i)$