27916번 - 아파트 단지 서브태스크

문제

설곽국에서 가장 긴 직선 도로인 예지로 주변에는 $N$개의 아파트가 있습니다. 각 아파트는 위치 순서대로 1ドル$동부터 $N$동까지 번호가 붙여져 있으며, $i$동의 위치는 도로 시작점에서부터 $A_i$ 만큼 떨어져 있습니다.

아파트가 늘어남에 따라 아파트 단지를 만들어 관리하기 편하게 하려고 합니다. 모든 아파트는 정확히 하나의 아파트 단지에 속해야 하고, 한 아파트 단지는 $M$개 이상의 연속된 번호를 가진 아파트로 이루어져야 합니다. 어떤 아파트 단지가 $L$동부터 $R$동까지의 아파트로 이루어질 때, 이 아파트 단지의 크기는 양끝 아파트 사이의 거리, 즉 $A_R - A_L$로 정의됩니다.

계획이 알려지자, 주민들은 아파트 단지 내에서 운동이나 교류를 하기 위해 모든 아파트 단지의 크기를 $X_i$ 이하로 제한해 달라는 요청을 했고, 그 결과 $Q$개의 요청이 모였습니다. 당신은 각각의 요청이 실현 가능한지를 판별하는 프로그램을 작성해야 합니다.

입력

첫 줄에 세 정수 $N,ドル $M,ドル $Q$가 띄어쓰기를 사이에 두고 주어집니다.

둘째 줄에는 각 아파트의 위치를 나타내는 $N$개의 정수 $A_1,ドル $A_2,ドル $\cdots,ドル $A_N$이 띄어쓰기를 사이에 두고 주어집니다.

셋째 줄에는 요청에 대한 정보를 나타내는 $Q$개의 정수 $X_1,ドル $X_2,ドル $\cdots,ドル $X_Q$가 띄어쓰기를 사이에 두고 주어집니다.

출력

길이 $Q$의 문자열을 출력합니다. 문자열의 $i$번째 문자는, $i$번째 요청을 만족하는 아파트 단지 구성이 존재할 경우 '1', 그렇지 않은 경우 '0'이어야 합니다.

제한

• 1ドル \le N \le 3 \times 10^5$
• 1ドル \le M \le N$
• 1ドル \le Q \le 3 \times 10^5$
• 1ドル \le A_i \le 10^9$ (1ドル \le i \le N$)
• $A_i < A_{i+1}$ (1ドル \le i < N$)
• 0ドル \le X_i \le 10^9$ (1ドル \le i \le Q$)

서브태스크

힌트