描述

L国军队的n名士兵打算举办一次游行。在首长到来检阅之前,士兵们已经站成了一排,其中第i (1<=i<=n) 名士兵的身高为a[i]。首长到来之后,打算对队伍进行调整。他认为一支美观的队伍应该由m名士兵组成,其中第i (1<=i<=m) 名士兵的身高为b[i]。他希望从当前的队伍中选出若干段连续的士兵(各段之间不能重叠),每段包含m名士兵,并且每段士兵的身高都符合美观的要求。然而这几乎是不可能实现的……
于是首长可能会降低要求——如果选出的某段士兵为[k,k+m-1],对于这段士兵中的第i名和第j名 (1<=i,j<=m),如果a[k+i-1]、a[k+j-1] 的大小关系与b[i]、b[j] 的大小关系是相同的(都是大于关系、或者都是相等关系、或者都是小于关系),那么这段士兵组成的队伍就是美观的。现在请你计算一下最多能选出多少段士兵吧。

输入格式

第一行三个整数n、m、t、p,分别表示士兵的总个数、选出的每段士兵的个数、士兵身高不会超过t、首长是否降低了要求。p=1表示首长降低了要求,p=0表示没有降低。
接下来有n个用空格或换行符隔开的整数ai。
接下来有m个用空格或换行符隔开的整数bi。

输出格式

一个整数,表示最多能选出的段数。

样例输入

10 5 10 1
2 4 2 4 2 4 2 4 2 4
1 2 1 2 1

样例输出

1

数据范围与约定

  • 对于10% 的数据,1<=m<=n<=100。
  • 对于另40% 的数据,p=0。
  • 对于100% 的数据,1<=m<=n<=10^5,1<=ai,bi<=t<=25,p=0或1。