La Paz, 볼리비아의 수도는 관광지로 유명하며 Mi Teleferico라는 공중 케이블카로도 잘 알려져 있습니다.

관광을 위해 La Paz를 방문한 여러분은 가능한 한 많은 관광지를 방문하고자 합니다. 이 문제에서는 다음과 같이 단순화한 상황을 고려합니다.

La Paz에는 고도가 증가하는 순서대로 번호가 1부터 N까지인 공중 케이블카 정거장이 있습니다.

1부터 M까지 번호가 매겨진 단방향 노선들이 있으며, 각 노선은 한 개의 케이블카 회사에 의해 운영됩니다. 회사들은 1부터 P까지 번호가 매겨져 있습니다.

노선 i (1 ≤ i ≤ M)는 정거장 Aᵢ에서 Bᵢ로 운행되며, 회사 Cᵢ가 관리합니다. (항상 Aᵢ < Bᵢ)

La Paz 교통국은 편리하게 이용할 수 있도록 무제한 이용권을 발행합니다. 각 이용권은 두 정수 l, r (1 ≤ l ≤ r ≤ P)로 구성되며, 이 이용권을 가진 사람은 회사 번호가 l, l+1, …, r 중 하나인 노선을 탈 수 있습니다. (한 이용권으로 여러 노선을 이용할 수 있음)

Q명의 관광객이 La Paz를 방문합니다. 관광객 j (1 ≤ j ≤ Q)는 초기 이용권 (L_j, R_j)과 X_j원의 현금을 가지고 있습니다.

각 관광객의 목표는 자신이 가진(또는 교환을 통해 얻은) 이용권을 사용하여, 정거장 1에서 출발해 해당 이용권으로 탈 수 있는 노선만 이용함으로써 모든 정거장에 도달할 수 있게 되는 것입니다.

관광객 j는 단 한 번, 아래 절차를 통해 자신의 이용권을 교환할 수 있습니다.

두 정수 l^′, r^′ (1 ≤ l^′ ≤ r^′ ≤ P)를 선택한다.
현재 이용권 (L_j, R_j)를 (l^′, r^′)로 교환하는데, 교환 비용은 |L_j − l^′| + |R_j − r^′|원이다.

각 관광객이 자신이 가진 현금 X_j 내에서 목표를 달성할 수 있는지 판별하는 프로그램을 작성하시오.

#8332 upload 15 done 5 how_to_reg 4 call_split Subtask

Mi Teleferico timer 2s memory 1024MB

#8332
Subtask

Mi Teleferico 2s 1024MB