Simultaneous Sugoroku

AtCoder

IDarc149_d

Time2000ms

Memory256MB

Difficulty—

There are $N$ pieces placed at integer coordinates on a number line. The coordinate of the $i$\-th piece is $X_i$. Let us move these pieces $M$ times as follows. * In the $i$\-th move, given a positive integer $D_i$, we move each piece as follows. * A piece whose coordinate is a negative integer is moved a distance of $D_i$ in the positive direction. * A piece whose coordinate is $0$ is not moved. * A piece whose coordinate is a positive integer is moved a distance of $D_i$ in the negative direction. Determine whether each piece arrives at the origin. If it does, print the number of moves after which it arrives there for the first time. Otherwise, print its coordinate after the $M$ moves. ## Constraints * $1\leq N\leq 3\times 10^5$ * $1\leq M\leq 3\times 10^5$ * $1\leq X_1 < \cdots < X_N \leq 10^6$ * $1\leq D_i \leq 10^6$ ## Input The input is given from Standard Input in the following format: $N$ $M$ $X_1$ $\ldots$ $X_N$ $D_1$ $\ldots$ $D_M$ [samples]

Samples

Input #1

6 4
2 4 6 8 10 12
8 2 5 7

Output #1

No -6
No -4
Yes 2
Yes 1
Yes 2
No 4

The coordinate of each piece changes as follows.

*   The $1$\-st piece: $\phantom{0}2\quad \longmapsto \quad -6\quad \longmapsto \quad -4\quad \longmapsto \quad \phantom{-}1 \quad \longmapsto \quad -6$.
*   The $2$\-nd piece: $\phantom{0}4 \quad \longmapsto \quad -4\quad \longmapsto \quad -2 \quad \longmapsto \quad \phantom{-}3 \quad \longmapsto \quad -4$.
*   The $3$\-rd piece: $\phantom{0}6 \quad \longmapsto \quad -2\quad \longmapsto \quad \phantom{-}0 \quad \longmapsto \quad \phantom{-}0 \quad \longmapsto \quad \phantom{-}0$.
*   The $4$\-th piece: $\phantom{0}8 \quad \longmapsto \quad \phantom{-}0\quad \longmapsto \quad \phantom{-}0 \quad \longmapsto \quad \phantom{-}0 \quad \longmapsto \quad \phantom{-}0$.
*   The $5$\-th piece: $10 \quad \longmapsto \quad \phantom{-}2\quad \longmapsto \quad \phantom{-}0 \quad \longmapsto \quad \phantom{-}0 \quad \longmapsto \quad \phantom{-}0$.
*   The $6$\-th piece: $12 \quad \longmapsto \quad \phantom{-}4\quad \longmapsto \quad \phantom{-}2 \quad \longmapsto \quad -3 \quad \longmapsto \quad \phantom{-}4$.

API Response (JSON)

{
  "problem": {
    "name": "Simultaneous Sugoroku",
    "description": {
      "content": "There are $N$ pieces placed at integer coordinates on a number line. The coordinate of the $i$\\-th piece is $X_i$. Let us move these pieces $M$ times as follows. *   In the $i$\\-th move, given a posi",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc149_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are $N$ pieces placed at integer coordinates on a number line. The coordinate of the $i$\\-th piece is $X_i$.\nLet us move these pieces $M$ times as follows.\n\n*   In the $i$\\-th move, given a posi...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments