有 颗红球排成一行，从左到右编号从 到 （含两端）。我们将进行 次操作，其中第 次操作将第 颗球涂成蓝色。所有操作结束后，所有球都会变成蓝色。
有 个编号从 到 （含两端）的传感器监控球的颜色。若第 颗球到第 颗球（含两端）里恰有一颗红球，则第 个传感器将进入激活状态；否则传感器将保持非激活状态。
问每次操作结束后，哪些传感器处于激活状态。
更具体地，设第 次操作结束后共有 个传感器处于激活状态，它们的编号是 。对于每个 ，输出 。特别地，定义 ，其中 是第一次操作之前处于激活状态的传感器数量，它们的编号为 。
有多组测试数据。第一行输入一个整数 表示测试数据组数。对于每组测试数据：
第一行输入两个整数 和 （）表示球的数量和传感器的数量。
对于接下来 行，第 行输入两个整数 和 （）表示第 个传感器的检测范围。
接下来的一行输入 个整数 （），其中 表示 加密后的 第 次操作。 的真实值等于 ，其中 是第 次操作后的答案，在上述描述中已有定义。这些加密后的操作强制您必须计算好当前操作的答案，才能处理下一个操作。保证解密后 互不相同。
保证所有数据 之和与 之和均不超过 。
每组数据输出一行 个由单个空格分隔的整数 。 的含义在上述描述中已有定义。
3 5 4 2 4 2 3 3 3 0 2 3 2 4 2 0 2 1 1 1 1 0 2 1 0 1 0 0
9 13 29 17 16 0 1 1 0 0 1 0
对于第一组样例数据：
