You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

众所周知，《YSZMNL》是一款架空虚构的桌游，在游戏中，玩家每进行一次操作都需要投掷$n$个骰子（偶数个）进行判定,每个骰子具有$m$面，如果点数足够高于阈值，则视为操作成功。 此时，youngmagician即将面临这款游戏中进行最后的boss战，为了给boss造成足够多的伤害，他需要尽可能的增大骰子的点数和。youngmagician拥有四个能力：

1，时空回溯，在一次骰子判定中，youngmagician可以投掷$t$次骰子，例如当$t$=2时，youngmagician在投掷一次后可以选择重投，或者直接进入下一步结算。

2,金手指。投掷骰子时，youngmagician左右手分别操控一半的骰子，使得每只手控制的一半骰子的投掷点数保持相同。假设$n$=4,那么只会出现1,1,2,2.等情况而不会出现,1,1,2,3这种情况。

3，概念压制，由于youngmagician的运气非常不好，往往投掷的点数很低；这个能力可以使得在进行投掷之前，直接把此次投掷的期望值（不一定是整数）直接当成投掷结果使用，例如，假设$k$=0,$t$=1,2个6面骰子，那么youngmagician的投掷结果就视为7。

4，连击，击败一名boss后，可以立即对下一名boss进行攻击的骰子判定。 易知,youngmagician想要无伤通过最后的boss战且血量极低，这就意味着如果youngmagician不能一次击杀某个Boss，他就会因为被boss进攻而失败，一场boss战共有$q$个boss,每个boss具有血量值$a$，请你帮忙计算youngmagician能够连续击杀多少个boss?

Input Format

4个整数$n,m,t,q$。分别表示骰子数量，骰子面数，重投次数，boss的数量。

接下来一行输入$q$个整数，分别表示每一个boss的血量

Output Format

一个整数，表示击败的boss的数量。

Sample

样例输入

2 6 1 3
1 8 2

样例输出

1  

样例解释，两个六面骰子的投掷一次的期望是7，比1大，比8小，youngmagcian在第二个Boss处失败。

Hint

对于所有数据，保证骰子数量$n$,$1\leq n \leq 10^8$;

骰子面数$m$,$1\leq m \leq 10^3$;

重投次数$t$,$1\leq t \leq 10^6$;

boss数量$q$,$1\leq q \leq 10^6$；

boss血量$a$,$1\leq a \leq 10^{12}$