国际象棋
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

你自己在一个 nm 列的棋盘上玩游戏,但这张棋盘是立起来的,棋子受到重力的作用,都掉落在对应列的最下方。换句话说,不在最后一行的棋子的下面都一定有棋子。

你一颗一颗的落子,依次按照黑棋白棋交替的顺序落子。当出现了 k 子连珠的局面时,游戏结束。k 子连珠指的是横竖斜共 8 个方向中有连续 k 颗棋子的颜色均相同。

现在有一份你落下 t 颗子的记录,每次操作在第 i 列顶端加入一颗棋子,奇数次落子时这颗子是黑棋,否则是白棋,请问游戏结束时你落下了多少颗棋子,以后的记录均没有意义,可以忽略。

你是一个严谨的人,在这份记录中游戏一定会结束且棋子不会堆叠超过 n 层。


输入描述:

第一行四个整数 n, m, k, t,接下来一行共 t 个数,依次代表每一次落子的 i


输出描述:

输出一个数,即游戏结束时棋盘上的棋子数量。
示例1

输入

复制
5 5 2 3
1 2 1

输出

复制
3