JOI 애비뉴는 동서 방향으로 길이가 L인 도로입니다. 이 도로의 서쪽 끝에서 l 미터 떨어진 지점을 "위치 l"이라고 합니다.

올해 JOI 애비뉴에서 첫 번째 마라톤 경주가 열릴 예정입니다. 이 경주는 일반적인 경주와는 다른 규칙을 가지고 있으며, 다음과 같이 설명됩니다:

경주 전에 N개의 공이 도로에 배치됩니다. i번째 공(1 ≤ i ≤ N)은 위치 Xi에 배치됩니다. 여러 개의 공이 같은 위치에 배치될 수 있습니다.

참가자는 지정된 위치에서 출발합니다.

참가자는 N개의 공을 모두 모은 후 지정된 위치로 돌아옵니다. 이 작업을 지정된 시간 내에 완료하면 경주를 완주한 것으로 간주됩니다. 단, 참가자가 공을 한 번 모은 후에는 그 공을 도로에 놓을 수 없으며, 그렇지 않으면 경주에서 실격됩니다.

출발 및 도착 위치와 시간 제한은 아직 발표되지 않았지만, Q개의 시나리오에서 선택될 것이라는 정보가 있습니다. j번째 시나리오(1 ≤ j ≤ Q)에서는 참가자가 위치 Sj에서 출발해 위치 Gj에서 경주를 마치며, 시간 제한은 Tj 초입니다.

Rie는 이 마라톤 경주에 참가합니다. 그녀는 공을 1개 모으는 데 1초가 걸립니다. 공을 x개 들고 있을 때, 1미터 이동하는 데 x+1초가 걸립니다.

JOI 애비뉴의 정보, 공의 위치, 그리고 시나리오가 주어졌을 때, 각 시나리오에 대해 Rie가 경주를 완주할 방법이 존재하는지 여부를 판단하는 프로그램을 작성하세요.

마라톤 경주 2 timer 1s memory 1024MB

마라톤 경주 2 1s 1024MB