題目描述

科學家正在研究一種微蟲的生長周期，並發現以下的一些規律：

• 微蟲的壽命是 𝐿 個周期
• 微蟲在生長到第 𝑀 個周期時就進入成熟期稱為成蟲。成蟲都會參與繁殖。
• 在每個周期內新出生的微蟲數目等於所有還生存的成蟲的數量的總和之 1/𝑃 取整。
• 剛出生的微蟲視為第一周齡的蟲體 (即沒有所謂 0 周齡的蟲)。
• 壽命到達 𝐿 周齡的成蟲會參與一生中的最後一次繁殖, 然後在周期末自然死亡。
• 在蟲群中, 不定期會出現一次病毒, 每次病毒出現時就會有以下結果:

  • 只有成蟲才會感染到這種病毒, 新感染到病毒的成蟲每個周齡群(即同一周齡的成蟲的群體) 中都會死去該周齡群的一半 (取整數, 如該群的數目為9, 則會死4 餘下5, 若數目為10,則死去和餘下的數目相同)。

  • 曾感染病毒的生還者會終身免疫, 即在自然老死前再也不會感染病毒, 也就不會因感染病毒而死亡 (當然, 它們還是會因周齡到 𝐿 而自然老死)。

  • 因病毒而死亡的情況會發生在繁殖完成後及自然老死前。

  • 病毒在一個周期內只會出現最多一次。

為方便計算我們假設以上的所有數目都是準確的。即的生長沒有不確定性或隨機性。

在實驗開始時, 我們有 𝑁 隻微蟲, 且所有的微蟲都是剛出生的第一周期蟲。在實驗期間, 科學家觀察到有 𝑄 次的病毒出現, 科學家記錄了病毒出現的時間, 他們想知道在病毒出現的那個周期的期未, 跟據上述的生長規則, 蟲群生還的總數目應為多少 (生還的數目包括周齡為 𝐿 的, 在該周期末將會自然死亡的生還者及在當周期剛出生的蟲在內)。

輸入格式

• 輸入的第一行有 5 個正整數 𝑁 𝐿 𝑀 𝑃 𝑄, 它們的代表的意義見上面的描述。
• 接下來有 𝑄 行, 每行有一個正整數 𝑡, 它代表在第 𝑡 個周期時, 病毒出現了一次。而實驗開始時視為第一個周期。

其中, 病毒出現的周期記錄時間未必一定是順時間序。但可以保證輸入中沒有重複出的周期 𝑡, 且所病毒出現的周期都有包括在輸入資料內。

輸出格式

輸出應有 𝑄 行, 每行有一個非負整數。它順序對應輸入的每次病毒出現時, 在該周期未還生存的蟲的總數。

這個總數包括該周期出生的蟲, 還生存的成年蟲包括周齡為 𝐿 的成年蟲在內。

Samples

["99 4 3 2 3\r\n5\r\n6\r\n10","99 4 3 2 3\r\n10\r\n5\r\n6"]

["98\r\n111\r\n84","84\r\n98\r\n111"]

提示

對應於以上的輸入, 蟲的周期變代如下:

其中, 當病毒在第6周期出現時, 5周齡的蟲群因是病毒生還者, 所以它們不會受感染因而數目保持為25。

• 1 ≤ 𝑁 ≤ 1,000, 4 ≤ 𝐿 ≤ 2,000, 1 𝑡 ≤ 150,000
• 有20分的數據中, 其 𝑡 的值是按時間順序排列在輸入檔案中的
• 有60分的數據中 𝑄 ≤ 20,000
• 有80分的數據中 𝑄 ≤ 60,000

原始資料

• Zero1 題號：b089
• Hydro 題號：Z1089
• Locale：zh_TW
• Display：open