Underclued

AtCoder

IDarc186_a

Time2000ms

Memory256MB

Difficulty—

For two $N \times N$ matrices $A$ and $B$ whose elements are $0$ or $1$, we say that $A$ and $B$ are **similar** if they satisfy the following conditions: * The sums of corresponding rows are equal. That is, $A_{i,1} + \dots + A_{i,N} = B_{i,1} + \dots + B_{i,N}$ for any $i=1,\dots,N$. * The sums of corresponding columns are equal. That is, $A_{1,j} + \dots + A_{N,j} = B_{1,j} + \dots + B_{N,j}$ for any $j=1,\dots,N$. Furthermore, for an $N \times N$ matrix $A$ whose elements are $0$ or $1$, and integers $i,j$ ($1 \leq i,j \leq N$), we say that the element at row $i$ column $j$ is **fixed** if $A_{i,j} = B_{i,j}$ holds for any matrix $B$ that is similar to $A$. Answer the following $Q$ queries: * The $i$\-th query: If there exists an $N \times N$ matrix whose elements are $0$ or $1$ such that exactly $K_i$ elements are fixed, output `Yes`; otherwise, output `No`. ## Constraints * $2 \le N \le 30$ * $1 \le Q \le N^2+1$ * $0 \le K_i \le N^2$ * $K_i \ne K_j (1 \le i < j \le Q)$ * All inputs are integers ## Input The input is given from Standard Input in the following format: $N$ $Q$ $K_1$ $K_2$ $\vdots$ $K_Q$ [samples]

Samples

Input #1

Output #1

Yes
Yes
No

Query 1: For example, the following matrix $X$ has exactly $0$ fixed elements.

1 0 0
0 1 0
0 0 1

This is because all the following matrices, obtained by cyclically shifting the columns, are similar to $X$, and each element can be either $0$ or $1$.

0 0 1
1 0 0
0 1 0

0 1 0
0 0 1
1 0 0

Query 2: For example, the following matrix $X$ has exactly $9$ fixed elements.

0 0 1
0 1 1
1 1 1

This is because no other matrix similar to $X$ exists, and all elements are fixed.
Query 3: No matrix exists with exactly $7$ fixed elements.

Input #2

Output #2

No
Yes
No
Yes
No
Yes

API Response (JSON)

{
  "problem": {
    "name": "Underclued",
    "description": {
      "content": "For two $N \\times N$ matrices $A$ and $B$ whose elements are $0$ or $1$, we say that $A$ and $B$ are **similar** if they satisfy the following conditions: *   The sums of corresponding rows are equal",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc186_a"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "For two $N \\times N$ matrices $A$ and $B$ whose elements are $0$ or $1$, we say that $A$ and $B$ are **similar** if they satisfy the following conditions:\n\n*   The sums of corresponding rows are equal...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments