注：本题为J题“仓鼠玩炉石传说”的升级版，请确保自己理解“超杀”机制再开此题。

“炉石传说真的好玩吗？”

p2oileen 喜欢和 hzwer 一起搓炉石，但总是被暴打。

现在 p2oileen 在和 hzwer 对战。她的战场上只剩下了一只攻击值为a

hzwer先开始回合，在每次p2oileen的回合结束后，请你输出当前hzwer存活的随从数量。

注：本题中忽略敌方随从的攻击值，即火焰传令官在攻击时不会因掉血而死亡。

第一行会有三个整数n,m,a,k

在接下来一行，有n个整数H₁…H_n。分别表示从左到右的hzwer的随从的血量。

在接下来的m行，每行有四个正整数L_i,R_i,B_i,P_i，分别代表hzwer加血的随从编号区间左端点，右端点，加血量，以及p2oileen命令火焰传令官攻击的随从编号。

对于所有数据，1≤n,m,L_i,R_i≤2×10⁵,1≤a,k,H_i,B_i≤10⁹。