A. Cursed Query

Codeforces

IDCF10057A

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

De Prezer loves movies and series. He has watched the Troy for like 100 times and also he is a big fan of Supernatural series.So, he did some researches and found a cursed object which had n lights on it and initially all of them were turned off.Because of his love to the Troy, he called that object Troy. He looked and saw a note on it in Khikulish (language of people of Khikuland): "Ma in hame rah umadim, hala migi ... ? ... Mage man De Prezer am k mikhay mano ... ? .... Man se sale ... To boro .... beshur manam miram ... o mishuram". He doesn't know Khikulish, so just ignored the note and tested the Troy. He realized that the light number i stays turned on for exactly ai seconds, and then it turns itself off (if it is turned on, in time t, in time t + ai - 1 it will be turned on, but on time t + ai it won't be) and the next light will be turned on (if i < n, next light is the light number i + 1, otherwise it is light with number 1). For example if n = 2 and we turn on the first light in time 0, it will be turned on in hole interval [0, a1) and in hole interval [a1, a1 + a2) the second light will be turned on and so on. In time 0 he turns on the light number 1. De Prezer also loves query.So he gives you q queries.In each query he will give you integer t (the time a revengeful ghost attacked him) and you should print the number of the light that is turned on, in time t. The first line of input contains two integers n and q. The second line contains n space separated integers, a1, a2, ..., an . The next q lines, each line contains a single integer t . 1 ≤ n, q ≤ 105 1 ≤ ai ≤ 109 1 ≤ t ≤ 1018 For each query, print the answer in one line. ## Input The first line of input contains two integers n and q.The second line contains n space separated integers, a1, a2, ..., an .The next q lines, each line contains a single integer t .1 ≤ n, q ≤ 1051 ≤ ai ≤ 1091 ≤ t ≤ 1018 ## Output For each query, print the answer in one line. [samples]

**Definitions** Let $ n \in \mathbb{Z} $ be an input integer with $ 1 \leq n \leq 10^{1000} $. Let $ h = 31 $ be the holy number. **Constraints** $ n $ is given as a decimal string of up to 1001 digits. **Objective** Accept $ n $ if and only if $ 31 \mid n $, i.e., $ n \equiv 0 \pmod{31} $.

API Response (JSON)

{
  "problem": {
    "name": "A. Cursed Query",
    "description": {
      "content": "De Prezer loves movies and series. He has watched the Troy for like 100 times and also he is a big fan of Supernatural series.So, he did some researches and found a cursed object which had n lights on",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10057A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "De Prezer loves movies and series. He has watched the Troy for like 100 times and also he is a big fan of Supernatural series.So, he did some researches and found a cursed object which had n lights on...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be an input integer with $ 1 \\leq n \\leq 10^{1000} $.  \nLet $ h = 31 $ be the holy number.\n\n**Constraints**  \n$ n $ is given as a decimal string of up to 100...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments