Jade 正在玩弄物品和盒子。她想知道她拥有的物品是否能装进这些盒子里。场景描述如下。
Jade 有 $m$ 个盒子 $\mathcal{B} := \{ B_1, B_2, \dots, B_m \}$，它们彼此互不相同。尽管盒子的外观不同，但它们的大小统一为 $T$。另一方面，她有 $n$ 个物品 $\mathcal{I} := \{ I_1, I_2, \dots, I_n \}$，其中物品 $I_j$ 的大小 $a_j$ 为 $s_1$ 或 $s_2$ 中的某一个。换句话说，对于所有 $1 \le j \le n$，都有 $a_j \in \{ s_1, s_2 \}$。此外，已知 $0 < s_1, s_2 \le T$ 且 $s_1, s_2 \notin (T/4, 3T/4)$。也就是说，对于 $i \in \{1, 2\}$，要么 $s_i \le T/4$，要么 $s_i \ge 3T/4$。
在 Jade 的装箱经验法则中，并非每个物品都能放入每个盒子。具体来说，她为每个物品 $I_j$ 关联了一个子集 $P_j \subseteq \mathcal{B}$，表示允许放置物品 $I_j$ 的盒子集合。准确地说，物品 $I_j$ 可以放入盒子 $B_i$ 当且仅当 $B_i \in P_j$。为方便起见，对于任何 $B_i \in \mathcal{B}$，定义 $P_i^{-1} := \{ I_j \in \mathcal{I} : B_i \in P_j \}$ 为允许放入盒子 $B_i$ 的物品集合。
在这种情况下，Jade 想知道是否可以将所有物品装入盒子，使得每个盒子中物品的总大小不超过 $T$。换句话说，Jade 想知道是否存在一个分配函数 $\sigma: \mathcal{I} \mapsto \mathcal{B}$ 满足：
- 对于任何 $1 \le j \le n$，仅当 $B_i \in P_j$ 时，$\sigma(I_j) = B_i$。
- 对于任何 $1 \le i \le m$，$\sum_{I_j \in \sigma^{-1}(B_i)} a_j \le T$。
特别地，如果不存在这样的分配，则称盒子大小 $T$ 是不可行的。
众所周知，证明上述场景中任何 $T \ge 0$ 不可行的一种方法是展示一组变量 $\alpha_j$ 和 $\beta_i$（对于所有 $I_j \in \mathcal{I}, B_i \in \mathcal{B}$），使得下面列出的 LP-(t)（其中 $t := T$）中的线性约束得到满足。
换句话说，存在一组关于物品和盒子大小的有效估计，使得每当一个物品组合 $C$ 的总大小不超过盒子 $B_i$ 的大小时，它们的估计总大小也不超过盒子 $B_i$ 的估计大小。此外，物品的估计总大小严格大于盒子的估计总大小。
$$ \sum_{1 \le j \le n} \alpha_j > \sum_{1 \le i \le m} \beta_i \quad \text{LP-(t)} $$ $$ \sum_{I_j \in C} \alpha_j \le \beta_i, \quad \text{对于任何 } 1 \le i \le m \text{ 以及任何 } C \subseteq P_i^{-1} \text{ 满足 } \sum_{I_j \in C} a_j \le t. $$
Jade 很难找到这样一组变量。有一天，Jade 的好朋友 Mike 过来并说道：
你给出的实例很难装箱！为什么不试着证明盒子大小 $(1 + 3/4) \cdot T$ 是可行的呢？
虽然使用扩大到 $(1 + 3/4) \cdot T$ 的盒子更容易，但 Jade 坚持要求每个盒子包含的大小严格大于 $T/4$ 的物品不得超过一个！
基于上述信息，本题的任务是帮助 Jade 计算以下两者之一：
- 一个针对扩大后的盒子大小 $(1 + 3/4) \cdot T$ 的分配 $\sigma$，使得没有任何盒子包含超过一个大小严格大于 $T/4$ 的物品，或者
- 一组满足 LP-(t)（其中 $t := T$）的 $\alpha_j$ 和 $\beta_i$，证明盒子大小 $T$ 对这些物品是不可行的。
输入格式
第一行包含两个整数 $n$ 和 $m$，分别表示物品的数量和盒子的数量。接下来有 $n$ 行，每行描述 $n$ 个物品的参数。具体来说，第 $j$ 行以两个整数 $a_j$ 和 $p_j$ 开头，分别表示 $I_j$ 的大小和 $P_j$ 的基数。随后是 $p_j$ 个整数，表示 $P_j$ 中盒子的索引。最后一行包含一个整数 $T$。
你可以假设盒子的索引从 1 到 $m$ 编号。
输出格式
根据结果的不同，输出格式也不同。
如果找到了盒子大小 $(1 + 3/4) \cdot T$ 的分配，则在第一行打印字符串 "Assignment"。在第二行打印 $n$ 个整数，表示 $n$ 个物品所放置的盒子索引。如果有多个答案，打印其中任意一个即可。
另一方面，如果找到了满足 LP-(t)（其中 $t := T$）的 $\alpha_j$ 和 $\beta_i$ 集合，则在第一行打印字符串 "Proof"。在接下来的两行中分别打印所有 $1 \le j \le n$ 的 $\alpha_j$ 值和所有 $1 \le i \le m$ 的 $\beta_i$ 值。如果有多个解，打印满足以下两个条件的任意一个即可：
- 对于所有 $1 \le j \le n$ 和 $1 \le i \le m$，$\alpha_j$ 和 $\beta_i$ 均为非负整数。
- $\max (\max_{1 \le j \le n} \alpha_j, \max_{1 \le i \le m} \beta_i) \le 3 \times 10^5$。
数据范围
- $1 \le n \le 100, 1 \le m \le 100$。
- $T$ 是 4 的倍数。此外，$1 \le T \le 10^5$。
- 对于 $i \in \{1, 2\}$，必须满足 $1 \le s_i \le T/4$ 或 $3T/4 \le s_i \le T$。
- 对于所有 $1 \le j \le n$，$a_j \in \{s_1, s_2\}$。
对于输出，必须满足以下条件：
- 对于所有 $1 \le j \le n$ 和 $1 \le i \le m$，$\alpha_j$ 和 $\beta_i$ 均为非负整数。
- $\max (\max_{1 \le j \le n} \alpha_j, \max_{1 \le i \le m} \beta_i) \le 3 \times 10^5$。
样例
样例输入 1
3 3 4 2 1 2 4 2 2 3 4 2 3 1 4
样例输出 1
Assignment 1 2 3
样例输入 2
4 3 4 2 1 2 4 2 2 3 4 2 3 1 4 3 1 2 3 4
样例输出 2
Proof 1 1 1 1 1 1 1