지하 비밀 기지 침략 대작전

경기과학고등학교의 지하 기지에는 수억 원 가치의 보석이 숨겨져 있다. 이 사실을 알게 된 엘투는 경기과학고등학교 지하 기지를 몰래 침입하여 보석을 훔치려고 한다. 하지만, 엘투는 곧 지하 기지가 매우 복잡한 구조로 이루어져 있다는 사실을 알게 된다. 지하 기지는 방과 방 사이가 몇몇 통로로 연결된 그래프 모양을 하고 있다. 방의 개수는 $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급 한자를 넣으려고 했으나 실패했다.