알파카 경현이는 매우 어려운 리듬 게임을 하고 있다.

이 게임에는 총 \(N\)개의 노트가 등장한다. \(i\)번째 노트는 시간 구간 \([L_i, R_i]\) 안에 클릭해야 처리할 수 있다. 즉, 알파카가 어떤 시각 \(t\)에 클릭했을 때

$$ L_i \le t \le R_i $$

를 만족하면 \(i\)번째 노트를 처리할 수 있다.

하지만 알파카는 아무 시각에나 정확히 클릭할 수 없다. 알파카가 화면을 보고 반응할 수 있는 시각은 모니터의 프레임이 갱신되는 시각뿐이다.

주사율이 \(F\) Hz인 모니터를 사용하면, 프레임은 \(\frac{1}{F}\)초마다 한 번씩 갱신된다. 또한 게임 시작 시각과 모니터의 프레임 갱신 시각은 어긋나 있을 수 있다.

따라서 알파카가 클릭할 수 있는 시각들은 어떤 실수 \(x\)에 대해 다음과 같이 표현된다.

$$ x+\frac{k}{F} $$

여기서 \(k\)는 음이 아닌 정수이고,

$$ 0 \le x < \frac{1}{F} $$

이다.

알파카는 게임을 시작하기 전에 \(x\)를 원하는 값으로 한 번 정할 수 있다. 단, 게임이 시작된 뒤에는 \(x\)를 바꿀 수 없다.

알파카가 모든 노트를 처리하려면, 모든 \(i\)에 대해 \([L_i, R_i]\) 안에 클릭 가능한 시각이 적어도 하나 존재해야 한다.

즉, 모든 \(i\)에 대해 어떤 음이 아닌 정수 \(k\)가 존재하여

$$ L_i \le x+\frac{k}{F} \le R_i $$

를 만족해야 한다.

알파카는 여러 개의 모니터를 후보로 가지고 있다. \(j\)번째 모니터의 주사율은 \(F_j\) Hz이다.

각 후보 모니터에 대해, 모든 노트를 처리할 수 있도록 하는 \(x\)를 정할 수 있는지 판정하여라.

시간은 모두 마이크로초 단위의 정수로 주어진다. 즉, 입력으로 주어지는 \(L_i, R_i\)는 실제 시간

$$ \frac{L_i}{10^6}, \frac{R_i}{10^6} $$

초를 의미한다.

• $$ 1 \le N \le 200{,}000 $$

• $$ 1 \le Q \le 50 $$

• $$ 0 \le L_i \le R_i \le 10^{12} $$

• $$ 1 \le F_j \le 10^{12} $$

• 모든 입력값은 정수이다.

첫째 줄에 노트의 개수 \(N\)과 후보 주사율의 개수 \(Q\)가 주어진다.

다음 \(N\)개의 줄에는 두 정수 \(L_i, R_i\)가 공백으로 구분되어 주어진다.

이는 \(i\)번째 노트를 실제 시간 구간

$$ \left[\frac{L_i}{10^6}, \frac{R_i}{10^6}\right] $$

초 안에 클릭해야 함을 의미한다.

다음 \(Q\)개의 줄에는 정수 \(F_j\)가 주어진다.

총 \(Q\)개의 줄을 출력한다.

\(j\)번째 줄에는 주사율이 \(F_j\) Hz인 모니터로 모든 노트를 처리할 수 있으면 YES, 그렇지 않으면 NO를 출력한다.

rip 작성

출처 알파카컵 2회