第一行包含四个以空格分隔的整数 n、m、c、k。分别表示动物园中动物数量、《饲养指南》要求数、饲料种数与动物编号的二进制表示位数。
第二行 n 个以空格分隔的整数，其中第 i 个整数表示 ai。
接下来 m 行，每行两个整数 pi，qi 表示一条要求。
数据保证所有 ai 互不相同，所有的 qi 互不相同。
对于 100%的数据：0≤n,m≤106，0≤k≤64，1≤c≤108
3 3 5 4
1 4 6
0 3
2 4
2 513
【样例 1 解释】
动物园里饲养了编号为 1、4、6 的三种动物，《饲养指南》上 3 条要求为：
1. 若饲养的某种动物的编号的第 0 个二进制位为 1，则需购买第 3 种饲料。
2. 若饲养的某种动物的编号的第 2 个二进制位为 1，则需购买第 4 种饲料。
3. 若饲养的某种动物的编号的第 2 个二进制位为 1，则需购买第 5 种饲料。
饲料购买情况为：
1. 编号为 1 的动物的第 0 个二进制位为 1，因此需要购买第 3 种饲料；
2. 编号为 4、6 的动物的第 2 个二进制位为 1，因此需要购买第 4、5 种饲料。
由于在当前动物园中加入一种编号为 0,2,3,5,7,8, ⋯ ,15 之一的动物，购物清单都不会改变，因此答案为 13。
【样例 2 输入】
2 2 4 3 1 2 1 3 2 4
【样例 2 输出】
2