Max Matrix 2

AtCoder

IDabc433_e

Time2000ms

Memory256MB

Difficulty—

You are given integers $N,M$, a sequence of $N$ integers $X=(X_1,X_2,\ldots,X_N)$, and a sequence of $M$ integers $Y=(Y_1,Y_2,\ldots,Y_M)$. Determine whether there exists an $N$ row by $M$ column integer matrix $A=(A_{i,j})$ $(1\le i\le N,\ 1\le j\le M)$ that satisfies all of the following conditions, and if so, find one such matrix. * $1\le A_{i,j} \le N\times M$ * All $N\times M$ elements of $A_{i,j}$ are distinct. * $\displaystyle \max_{1\le j\le M} A_{i,j} = X_i$ for $i=1,2,\ldots,N$. * $\displaystyle \max_{1\le i\le N} A_{i,j} = Y_j$ for $j=1,2,\ldots,M$. You are given $T$ test cases; solve each of them. ## Constraints * $1\le T\le 10^5$ * $1\le N,M$ * The sum of $N\times M$ over all test cases is at most $2\times 10^5$. * $1\le X_i,Y_j\le N\times M$ * All input values are integers. ## Input The input is given from Standard Input in the following format: $T$ $\text{case}_1$ $\text{case}_2$ $\vdots$ $\text{case}_T$ Each test case is given in the following format: $N$ $M$ $X_1$ $X_2$ $\ldots$ $X_N$ $Y_1$ $Y_2$ $\ldots$ $Y_M$ [samples]

Samples

Input #1

3
2 3
5 6
5 3 6
3 3
5 4 6
6 2 4
5 4
18 20 19 14 17
18 20 14 15

Output #1

Yes
5 1 4
2 3 6
No
Yes
18 12 4 9
13 20 1 10
16 19 6 8
2 5 14 3
11 17 7 15

Consider the first test case.
In the sample output, all elements of $A$ are between $1$ and $6$ and are distinct, and furthermore,

*   $\displaystyle \max_{1\le j\le 3} A_{1,j} =\max \lbrace 5,1,4\rbrace = 5 = X_1$
*   $\displaystyle\max_{1\le j\le 3} A_{2,j} =\max \lbrace 2,3,6\rbrace = 6 = X_2$
*   $\displaystyle\max_{1\le i\le 2} A_{i,1} =\max \lbrace 5,2\rbrace = 5 = Y_1$
*   $\displaystyle\max_{1\le i\le 2} A_{i,2} =\max \lbrace 1,3\rbrace = 3 = Y_2$
*   $\displaystyle\max_{1\le i\le 2} A_{i,3} =\max \lbrace 4,6\rbrace = 6 = Y_3$

so all conditions are satisfied.
Other outputs, such as the following, are also accepted.

Yes
5 3 1
4 2 6

API Response (JSON)

{
  "problem": {
    "name": "Max Matrix 2",
    "description": {
      "content": "You are given integers $N,M$, a sequence of $N$ integers $X=(X_1,X_2,\\ldots,X_N)$, and a sequence of $M$ integers $Y=(Y_1,Y_2,\\ldots,Y_M)$. Determine whether there exists an $N$ row by $M$ column inte",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc433_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given integers $N,M$, a sequence of $N$ integers $X=(X_1,X_2,\\ldots,X_N)$, and a sequence of $M$ integers $Y=(Y_1,Y_2,\\ldots,Y_M)$.\nDetermine whether there exists an $N$ row by $M$ column inte...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments