지하 비밀 기지 침략 대작전

경기과학고등학교의 지하 기지에는 수억 원 가치의 보석이 숨겨져 있다. 이 사실을 알게 된 엘투는 경기과학고등학교 지하 기지에 몰래 침입하여 보석을 훔치려고 한다. 하지만 엘투는 곧 지하 기지가 매우 복잡한 구조로 되어 있다는 사실을 알게 된다. 지하 기지는 방과 방 사이가 몇몇 통로로 연결된 그래프 모양이다. 방의 개수는 $N$개이고, 통로의 개수는 $M$개이다. 그리고 철저한 보안을 위해 각각의 통로는 도어락으로 단단히 잠겨 있다. 통로 중에는 같은 방으로 다시 돌아오는 것도 존재할 수 있다.

도어락을 여는 도구로 총 $K$가지의 서로 다른 카드 키가 있다. 카드 키를 구분하기 위해 각 카드 키에는 타입이라 부르는, $K$ 이하의 양의 정수가 부여되어 있다. $i$번째 통로의 도어락에는 두 정수 $L_i$, $R_i$가 배정되어 있다. (단, $1 \leq i \leq M$, $1 \leq L_i \leq R_i \leq K$) 이는 엘투가 타입 $L_i$, 타입 $L_i + 1$, $\cdots$, 타입 $R_i$의 카드 키 중 하나라도 가지고 있다면 $i$번째 통로의 도어락을 열 수 있다는 뜻이다. 카드 키는 영구적으로 사용할 수 있다.

엘투는 지하 기지의 외형에 대한 정보는 모두 구해 놓았지만, 아직 보석의 정확한 위치는 모른다. 심지어 아직 엘투의 수중에는 $K$종류의 카드 키조차 없다. 따라서 이 대작전을 시행하기에 앞서, 엘투는 $Q$번의 시뮬레이션으로 각각의 상황마다 작전의 성공 여부를 판단하고자 했다.

$j$번째 시뮬레이션은 다음과 같이 진행된다. (단, $1 \leq j \leq Q$) 각 시뮬레이션은 네 정수 $X_j$, $Y_j$, $U_j$, $V_j$로 이루어진다. (단, $1 \leq X_j \leq N$, $1 \leq Y_j \leq N$, $1 \leq U_j \leq V_j \leq K$) 이는 엘투가 $X_j$번째 방에서 출발하여 보석이 있는 $Y_j$번째 방에 도달하고자 함을 뜻한다. 이때 $j$번째 시뮬레이션은 엘투가 타입 $U_j$, 타입 $U_j + 1$, $\cdots$, 타입 $V_j$의 카드 키를 모두 가지고 있을 때 보석이 있는 방에 도달하는 경로가 있는지 판단해야 한다.

첫 번째 줄에 $N$, $M$, $K$가 공백으로 구분되어 주어진다. 각각 방의 개수, 통로의 개수, 카드 키의 총 종류를 의미한다.

두 번째 줄부터 $M$개의 줄 중 $i$번째 줄에 $A_i$, $B_i$, $L_i$, $R_i$가 공백으로 구분되어 주어진다. 이는 $i$번째 통로가 $A_i$번째 방과 $B_i$번째 방을 잇고 있음을 뜻한다. 또 $L_i$와 $R_i$는 $i$번째 통로의 도어락을 열 수 있는 카드 키의 타입에 대한 정보를 담고 있다.

그 다음 줄에는 $Q$가 주어진다.

그 다음 줄부터 $Q$개의 줄 중 $i$번째 줄에 시뮬레이션의 내용 $X_i$, $Y_i$, $U_i$, $V_i$가 공백으로 구분되어 주어진다.

첫 번째 줄부터 $Q$개의 줄 중 $j$번째 줄에 $j$번째 시뮬레이션의 답을 출력한다.

$j$번째 시뮬레이션에서 엘투가 보석에 도달할 수 있다고 판단되면 $1$을 출력한다. 그렇지 않다면 $0$을 출력한다.

• $1 \leq N \leq 50\,000$
• $1 \leq M \leq 50\,000$
• $1 \leq K \leq 10^9$
• $1 \leq Q \leq 100\,000$
• $1 \leq A_i, B_i \leq N$ (단, $1 \leq i \leq M$)
• $1 \leq L_i \leq R_i \leq K$ (단, $1 \leq i \leq M$)
• $1 \leq X_j, Y_j \leq N$ (단, $1 \leq j \leq Q$)
• $1 \leq U_j \leq V_j \leq K$ (단, $1 \leq j \leq Q$)

문제 제목에 1급 한자를 넣으려고 했으나 실패했다.