题目描述

有一种棋盘游戏：棋盘上有 $n$ 个格子，每个格子上可以堆叠若干个有颜色的筹码，只有每个格子中最上方的筹码的颜色是可见的。

参加游戏的每个玩家都有各自不同的一个目标颜色，以及一些彩色筹码。每个人只知道自己的目标颜色，但各自拥有的筹码颜色和数量都是公开的。每个回合中，所有玩家轮流在棋盘上选一个格子放置筹码，同时覆盖下方的筹码。游戏结束后，数出棋盘上可见筹码数最多的颜色，以该颜色为目标颜色的玩家即获胜。若该颜色不是任何玩家的目标颜色，或者棋盘上出现最多的颜色不唯一，则游戏平局。

现在，一局游戏进行到了最后，你和其他所有玩家都只剩最后一个筹码。现在恰好轮到你操作，在不知道其他人的目标颜色的前提下，你想知道你一共有哪些操作可以保证必胜。

输入格式

第一行 $4$ 个整数 $n,p,c,h$，分别表示棋盘格数、玩家数、筹码颜色总数和你的目标颜色；

第二行 $n$ 个整数 $b_i$，表示棋盘上现有的筹码颜色，棋盘格编号从 $1$ 开始；

第三行 $p$ 个整数 $l_i$，表示每个玩家的最后一枚筹码的颜色，玩家编号从你开始。

输出格式

第一行 $1$ 个整数 $w$，表示你有多少种必胜操作。

6 3 4 2
2 1 2 3 2 2
2 1 1

1

数据范围

对于 $100\%$ 的数据，$1\le N\le 10^6,1\le p\le 10^6,p\le c\le 10^6,1\le h\le c,1\le b_i\le c,1\le l_i\le c$。