TopCoder

User's AC Ratio

66.7% (6/9)

Submission's AC Ratio

44.1% (26/59)

Tags

Description

聖誕節的時候都有很多一串一串的燈泡,現在你家裡就掛了一串。

這一串燈泡總共有 n 顆燈泡,第 i (1≦i≦n)顆燈泡會固定亮t_i秒後熄滅t_i,接著再亮t_i秒後熄滅t_i秒……。

一開始所有的燈泡都是亮的。

那請問在 [k秒, k+1秒) 這段時間時,總共有幾顆燈泡亮著呢 ?

Input Format

輸入可能包含多筆測資,以 EOF 結束輸入。

每筆輸入的第一行依序是三個正整數,N、T、Q,

接下來的一行有 N 個數字,第 i 個數字代表 t_i,

接下來的那一行共有 Q 個數字,第 j 個數字 q_j 即詢問在 [q_j, q_j + 1) 的時間中有幾顆燈泡亮著。

條件限制:
1 ≦ N, Q ≦100,000
1 ≦ t_i ≦ T ≦ 5,000,000
0 ≦ q_j < T

Output Format

對於每一筆詢問請輸出一行,即詢問的那一秒有幾顆燈泡亮著。

每組測試資料後請輸出一個空白行。

Sample Input

3 6 6
1 2 3
0 1 2 3 4 5

1 2 2
1
0 1

Sample Output

3
2
2
0
2
1

1
0

Hints

對於第一筆範例測資來說:

      時間點
   0 1 2 3 4 5 6
燈 1│亮│ │亮│ │亮│ │
泡 2│亮│亮│ │ │亮│亮│
  3│亮│亮│亮│ │ │ │
總數: 3 3 2 0 2 1

Problem Source

原TIOJ1627 / Problem Setter: suhorng

Subtasks

No. Testdata Range Score
1 0 50
2 1 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1
1 10000 65536 262144 2