TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (7/7)

Submission's AC Ratio

28.1% (9/32)

Tags

Description

你各位知道,BK 跟 YP 分別是誰嘛?

BK ,身為 LYB 的假解王,是今年 IOICamp 負責講隨機、近似的講師。

YP ,身為 LYB 的專業碼農,是今年 IOICamp 負責講根號算法的講師。

BK 非常喜歡堅果(因為堅果很好吃),而 YP 非常喜歡莫隊(因為莫隊很有趣)。

因此,當莫隊遇上堅果時,會產生出什麼樣子的新題目呢?

現在 BK 和 YP 有 N 個堅果,第 i 個堅果的總類為 ai

BK 和 YP 在接下來的 Q 天內,每天都會一起決鬥一個問題。

在第 i 天的決鬥中,BK 和 YP 會考慮:如果一口氣把第 Li 個堅果到第 Ri 個堅果吃到肚子裡面,那麼吃進去的堅果是不是「平衡」的?

BK 和 YP 認為:如果吃進肚子的堅果,每一種種類的堅果都吃了 K 個倍數 個,那麼吃進去的堅果就是平衡的。注意到這個 K 值在 Q 天的決鬥中都是一樣的。

Input Format

輸入的第一行包含三個數字 N,K,Q ,分別代表堅果的數量、一個用於判斷「平衡」的參數,以及 BK 和 YP 要進行決鬥的天數。

接下來的一行,包含 N 個以空白隔開的正整數 a1,a2,,aNai 代表第 i 個堅果的種類。

接下來的 Q 行,第 i 包含兩個正整數 Li,Ri ,代表第 i 天決鬥所要的參數。

  • 1N,K,Q5×105
  • 1ai5×105
  • 1LiRiN

Output Format

輸出一個長度為 Q 的 01 字串 s1s2sQ 。如果在第 i 天的決鬥中,吃進肚子的堅果是「平衡」的,那麼 si 就是 1,否則 si 就是 0

Sample Input 1

10 2 10
1 2 3 2 4 4 3 1 3 1
1 8
1 10
5 6
1 4
5 10
2 7
1 7
8 9
7 9
3 7

Sample Output 1

1010110000

Hints

Problem Source

IOICamp 2020 Day3 pH

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~7 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2
1 1000 262144 65536 2
2 1000 262144 65536 2
3 1000 262144 65536 2
4 1000 262144 65536 2
5 1000 262144 65536 2
6 1000 262144 65536 2
7 1000 262144 65536 2