AT_bitflyer2018_qual_e 祝日

AtCoder国家的$1$年由$Y$周组成，一周由$W$天组成。也就是说，一年由$Y*W$天组成。另外，星期依次有$1$,$2$,$3$,$4$….$W$的号码。也就是说，对于每个$i$($1

第一行两个整数$Y$($1\le Y\le10^9$),$W$($1\le W\le10^5$)。 第二行三个整数$N$($1\le N\le50$),$M$($1\le M\le10^5$),$D$($1\le D\le Y\times M$)。 接下来$N$行，第$i+2$行为一个整数$A_i$($1\le A_i\le Y\times W$)。 接下来$M$行，第$i+n+2$行为两个整数$B_i$($1\le B_i\le M$)和$C_i$($1\le C_i\le M$)。

输出$W$行。在第$i$行($1

对于$600$分的测试数据满足$N=0$。 【样例解释 1】 例如，对于一年的第一天为星期三，则一年的第$4$,$5$,$6$,$9$天为节日。 注：本题满分700分。