U224154 【D&S R1-4】杰哥的疯狂星期四

v 杰哥 50，让他和阿伟快乐做游戏。

为了让各位更好地 AK，Danno 提供了[简化题意](https://www.luogu.com.cn/paste/l4y3q8s7)。 --- 杰哥和阿伟正在玩一种名叫作大超商的桌游。 --- ### 大超商说明书 欢迎游玩大超商。大超商是比其他桌游都刺激的一款双人桌游。 - 超商 超商是游戏的基本卡。超商有两个属性：价值 $v$ 和地段颜色 $c$。超商卡数量随意，但您和您的俏佳人应保证超商卡数量为**偶数**。 - 基础游玩方式 游戏前，游戏玩家分出先后手。接下来，先后手轮流选择一个超商归入自己。易得先后手分得的超商数量相同。 - 联动 当**相同地段颜色**的超商归入同一玩家时，就有可能产生联动。每一张联动具有三个属性 $i,j,v$。表示当超商 $i,j$ 归入同一玩家时，这张联动自动归入这名玩家，额外产生 $v$ 的价值。 - 分数判定 所有超商被两名玩家选择完以后，一名玩家的得分即为他拥有的超商价值和与联动价值和。 快开始您的大超商之旅吧。 --- 杰哥和阿伟准备玩一把有 $n$ 张超商与 $m$ 张联动的大超商。这些超商中只有 $0,1$ 两种地段颜色，并且两种地段颜色的超商数量相同。 杰哥爱幼，于是让阿伟先手。 同时杰哥非常懒，所以他为自己准备了 $n/2$ 个策略。策略可以用诸如 $(x,y)$ 的二元组表示，含义是「假如阿伟上一手选了 $x$ ，杰哥就选 $y$ ，反之亦然。」。每个超商都在这 $n/2$ 个策略中被包含了恰好一次。同时这些策略中 $x,y$ 地段颜色**不一样**。 再同时，假如游戏结束时存在没有被归入任何一方的联动卡，那么这些联动卡由于杰哥的力量**全部**无条件归入杰哥（价值依然计算）。 阿伟觉得大超商还不够刺激，于是和杰哥打赌说假如这盘**阿伟**以**最优策略**选择超商（即阿伟得分最高）时**杰哥**得分**恰好**为 $k$，杰哥就要给阿伟登 dua 郎。 杰哥很想登 dua 郎，于是杰哥在以上 $n,m$ 张中选择了 $s,t$ 张超商与联动卡，修改它们的 $v$ 为任意**非负整数值**。但是当杰哥拿起涂改液把卡涂了的时候，他发现自己好像并不知道怎么改。 构造一种改卡方案，让他们成功登 dua 郎。假如没有合法方案，输出 $-1$。

第一行五个整数 $n,m,s,t,k$。 接下来 $n-s$ 行，每行两个整数，第 $i$ 行描述一张固定的超商 $i$ 的 $c,v$。 接下来 $s$ 行，每行一个整数，第 $i$ 行描述一张可被修改的超商 $i+s$ 的 $c$。 接下来 $n/2$ 行，每行两个整数，第 $i$ 行描述一个策略 $(x,y)$。 接下来 $m-t$ 行，每行三个整数，第 $i$ 行描述一张固定的联动 $i$ 的 $i,j,v$。 接下来 $t$ 行，每行两个整数，第 $i$ 行描述一张可被修改的联动 $i+t$ 的 $i,j$。

你的输出应该有 $s+t$ 行，每行一个整数。 你应先输出 $s$ 行，第 $i$ 行描述超商 $i+s$ 的 $v$。 接下来输出 $t$ 行，第 $i$ 行描述超商 $i+t$ 的 $v$。 但假如没有合法方案，只输出一个整数 $-1$。

【样例解释】 按照构造的方案，此时阿伟选择超商 $2,3,6,7$，杰哥分到 $1,4,5,8$。 易得此时阿伟分数最大。杰哥此时分数为 $1+2+3+4=10=k$。 --- 【数据范围与提示】 本题采用 SPJ 评测，当且仅当你的方案满足题面所述要求时你才可以得到该测试点 $100\%$ 的分数。 **本题采用捆绑测试。** | Subtask 编号 | $n$ | $m$ | $k$ | $c_i$ | $v_i$ |分数| | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ | $\leq 100$ | $\leq 100$ | $\leq 2\times 10^3$ | $\in[0,1]$ | $\leq 20$ |$30$| | $2$ | $\leq 8\times 10^4$ | $\leq 8\times 10^4$ | $\leq 2\times 10^6$ | $\in[0,1]$ |$\leq 20$ |$70$| 对于 $100\%$ 的数据，$0\leq n\leq 8\times 10^4$，$0\leq m\leq8\times10^4$，$1\leq s\leq n$，$1\leq t\leq m$，$0\leq k\leq 2\times 10^6$，$c_i\in[0,1]$，$0\leq v_i\leq20$ 。