题目描述

$n$ 个人坐成一圈参与卡牌游戏，第 $i$ 个人的右手边坐着第 $(i\bmod n)+1$ 个人。每个人有一个属性 $a_i$，手中的牌也有一个属性 $b_i$，其中 $a_i,b_i$ 都在 $1$ 到 $k$ 之间。

卡牌游戏一共有 $m$ 轮，第 $i$ 轮有一个参数 $c_i$，在此轮中，每个人把自己手中的牌传给左边的人，并接过右边的人传来的牌，一共执行 $c_i$ 次，执行完后若手牌属性等于自己的属性，这个人将会淘汰，否则无事发生。淘汰后，他仍然参与后续的传牌环节。

直接统计最终没有被淘汰的人数太简单了，于是为了让游戏更有趣，大家决定让 $a_i$ 初始并不确定，此后将会有 $n$ 次主持人播报，每次给定 $x,y$，表示确定了 $a_x=y$，并且每个人恰好被一次播报提及，没有被确定属性的人视作 $a_i$ 在 $[1,k]$ 的整数中均匀随机。

你需要计算每次播报后，最终期望有多少人不被淘汰，答案对 $(10^9+7)$ 取模。

输入格式

第一行三个整数 $n,m,k$。

第二行 $n$ 个整数 $b_{1\cdots n}$。

第三行 $m$ 个整数 $c_{1\cdots m}$。

接下来 $n$ 行，每行两个整数 $x,y$。

输出格式

共 $n$ 行，第 $i$ 行一个整数表示第 $i$ 次播报结束后的答案。

10 9 10
7 8 7 9 6 7 6 7 8 8
365246423 114618008 92029097 544807439 782098289 580307098 424404832 105077914 812934361
9 8
8 7
2 9
3 7
7 9
1 6
5 9
6 9
4 8
10 7

200000007 5 100000006 900000011 700000009 500000007 600000008 400000006 200000004 2

数据范围

对于 $30\%$ 的数据，$n,m,k\leq 10$。

对于 $60\%$ 的数据，$n,m,k\leq 3000$。

对于 $100\%$ 的数据，$1\leq n\leq 3000$，$1\leq m,k\leq 4\times 10^5$，$1\leq b_i\leq k$，$1\leq c_i\leq 10^9$。