Inside or Outside

AtCoder

IDarc190_a

Time2000ms

Memory256MB

Difficulty—

There is an integer sequence $x = (x_1, \ldots, x_N)$, which is initialized with $x_1 = \cdots = x_N = 0$. You will perform $M$ operations on this integer sequence. In the $i$\-th operation, you are given an integer pair $(L_i, R_i)$ such that $1 \leq L_i \leq R_i \leq N$, and you must perform **exactly one** of the following three operations: * Operation $0$: Do nothing. This operation incurs a cost of $0$. * Operation $1$: For each integer $j$ with $1 \leq j \leq N$, if $L_i \leq j \leq R_i$ **holds**, set $x_j = 1$. This operation incurs a cost of $1$. * Operation $2$: For each integer $j$ with $1 \leq j \leq N$, if $L_i \leq j \leq R_i$ **does not hold**, set $x_j = 1$. This operation incurs a cost of $1$. Your goal is to make $x_1 = \cdots = x_N = 1$ hold at the end. Determine whether this goal can be achieved. If it can be achieved, present one way to achieve it where the total cost of the operations is minimized. ## Constraints * $1 \leq N \leq 1000000$ * $1 \leq M \leq 200000$ * $1 \leq L_i \leq R_i \leq N$ * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ $M$ $L_1$ $R_1$ $\vdots$ $L_M$ $R_M$ [samples]

Samples

Input #1

Output #1

2
2 0 1 0

In the sample output, $x$ changes as follows:

*   Initially, $x = (0,0,0,0,0)$.
*   In the 1st operation, Operation $2$ is performed. $x_1$ and $x_5$ become 1, so $x = (1,0,0,0,1)$.
*   In the 2nd operation, Operation $0$ is performed. $x$ remains $(1,0,0,0,1)$.
*   In the 3rd operation, Operation $1$ is performed. $x_1, x_2, x_3, x_4$ become 1, so $x = (1,1,1,1,1)$.
*   In the 4th operation, Operation $0$ is performed. $x$ remains $(1,1,1,1,1)$.

Input #2

Output #2

1
0 1 0 0

Input #3

5 2
1 3
2 5

Output #3

2
1 1

Input #4

5 2
1 3
2 4

Output #4

\-1

API Response (JSON)

{
  "problem": {
    "name": "Inside or Outside",
    "description": {
      "content": "There is an integer sequence $x = (x_1, \\ldots, x_N)$, which is initialized with $x_1 = \\cdots = x_N = 0$. You will perform $M$ operations on this integer sequence. In the $i$\\-th operation, you are g",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc190_a"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There is an integer sequence $x = (x_1, \\ldots, x_N)$, which is initialized with $x_1 = \\cdots = x_N = 0$.\nYou will perform $M$ operations on this integer sequence. In the $i$\\-th operation, you are g...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments