题目描述
从前,有 nnn 只萌萌的糖糖,他们分成了两组一起玩游戏。他们会排成一排,第$i$只糖糖会随机得到一个能力值$b_i$。从第$i$秒的时候,第$i$只糖糖就可以消灭掉所有排在他前面的和他不是同一组的且能力值小于他的糖糖。
为了使游戏更加有趣,糖糖的爸爸,娇姐,会发功$m$次,第$i$次发功的时间为$c_i$,则在第$c_i$秒结束后$b1,b2,...,b_{c_i}$都会增加 1.
现在,娇姐想知道在第$n$秒后,会有多少只糖糖存活下来。
输入格式
第一行只有一个整数 T(T<6)T(T<6)T(T<6),表示测试数据的组数。
第二行有两个整数 n,mn,mn,m。表示糖糖的个数以及娇姐发功的次数。($1 \leq n \leq 50000, 1 \leq m \leq 1000000$)
第三行到 n+2n+2n+2 行,每行有两个整数$a_i,b_i$,表示第$i$只糖糖属于那一组以及他的能力值。($0 \leq a_i \leq 1, 1 \leq b_i \leq 1000000$) 第 n+3n+3n+3 行到第 n+m+2n+m+2n+m+2 行,每行有一个整数$c_i$,表示GTW第 iii 次发功的时间.($1 \leq c_i \leq n$)
输出格式
总共T行,第i行表示第i组数据中,糖糖存活的个数。
1
4 3
0 3
1 2
0 3
1 1
1
3
4