407529: GYM102822 J Joy of Handcraft

Little Horse always does some handcrafts, which is full of joy. This time, he builds a circuit that can turn on and off the bulbs periodically.

There are $$$n$$$ bulbs in the circuit, the $$$i$$$-th of which has a period $$$t_i$$$ and a luminance $$$x_i$$$. Formally, the $$$i$$$-th bulb will be turned on from the $$$(2kt_i+1)$$$-th second to the $$$(2kt_i+t_i)$$$-th second, and it will be turned off from the $$$(2kt_i+t_i+1)$$$-th second to the $$$(2kt_i+2t_i)$$$-th second, $$$k=0,1,2,\dots$$$ When the $$$i$$$-th bulb is on, its luminance will be $$$x_i$$$, otherwise its luminance will be $$$0$$$.

Now, Little Horse wants to know, for each second from the first second to the $$$m$$$-th second, what's the maximum luminance among all the bulbs.

The first line of the input contains an integer $$$T$$$ ($$$1 \le T \le 100$$$) — the number of test cases.

The first line of each test case contains two integers $$$n,m$$$ ($$$1 \le n,m \le 10^5$$$) — the number of bulbs, and the number of integers you need to output. The sum of $$$n$$$ and the sum of $$$m$$$ will not exceed $$$2\times10^5$$$.

Then in the next $$$n$$$ lines, the $$$i$$$-th line contains two integers $$$t_i,x_i$$$ ($$$1 \le t_i,x_i \le 10^5$$$) — the period and the luminance of the $$$i$$$-th bulb.

The $$$x$$$-th test case begins with $$$Case$$$ #$$$x$$$:, and there follow $$$m$$$ integers. The $$$i$$$-th integer indicates the maximum luminance among all the bulbs in the $$$i$$$-th second. If no bulb is on in the $$$i$$$-th second, output $$$0$$$.

3
2 3
1 1
2 2
2 5
1 2
2 3
3 3
1 1
1 2
1 3

Case #1: 2 2 1
Case #2: 3 3 2 0 3
Case #3: 3 0 3