Problem: cold_storage (2019 finals)

Fred works the night shift in a refrigerator storage warehouse. It's not very
exciting work, but Fred has ways to pass the time when nobody's around. For
example, lifting fridges turns out to be an amazing bodybuilding method!

The warehouse consists of **N** sections in a row, numbered from 1 to **N**.
In each section _i_, there are initially **Fi** fridges, all arranged in a
single stack. The sections are intended to be separate from one another, and
only accessible from the outside. To that end, each pair of adjacent sections
are separated by a wall, for a total of **N**-1 walls. However, these walls
don't stretch all the way to the ceiling, and aren't necessarily all of the
same height. The wall between sections _i_ and _i_+1 has a height of **Hi**
fridge-heights (Fred has come to measure everything relative to fridge
dimensions). Fred's favourite pastime involves climbing over these walls to
get between the warehouse's sections!

Fred will begin by entering the warehouse in some section, carrying in some
number of new fridges from the outside (yes, he's become strong enough to
carry multiple fridges in his arms at once). When he's currently in a certain
section _s_ and is carrying _f_ fridges, he may perform any of the following
actions:

  * Pick up a fridge from section _s_'s stack of fridges, if it's non-empty. This decreases the number of fridges in that stack by 1, and increases _f_ by 1.
  * Add a fridge that he's carrying onto section _s_'s stack of fridges, if he's carrying at least one fridge. This decreases _f_ by 1, and increases the number of fridges in that stack by 1. 
  * Climb onto section _s_'s stack of fridges and jump over a wall into an adjacent section, if the number of fridges in that stack is at least as large as the height of that wall (in fridge-heights). This decreases or increases _s_ by 1. 

Fred's goal is to visit all **N** sections at least once each. He just needs
to decide which section he should initially enter and how many additional
fridges he should bring from the outside. He has **M** such possible starting
situations in mind, the _i_th of which involves him beginning in section
**Xi** while carrying **Yi** fridges. For each hypothetical starting
situation, please help Fred determine whether or not he will be able to visit
all **N** sections!

### Input

Input begins with an integer **T**, the number of warehouses Fred works at.  
For each warehouse, there is first a line containing the space-separated
integers **N** and **M**.  
Then follows a line with the **N** space-separated integers **F1** through
**FN**.  
Then follows a line with the **N** \- 1 space-separated integers **H1**
through **HN-1**.  
Then, **M** lines follow, the _i_th of which contains the space-separated
integers **Xi** and **Yi**.

### Output

For the _i_th warehouse, print a line containing "Case #_i_: " followed by a
string of **M** characters, the _i_th of which is "Y" if Fred can visit all
**N** sections from the _i_th starting situation, or "N" otherwise.

### Constraints

1 ≤ **T** ≤ 90  
2 ≤ **N** ≤ 8,000  
1 ≤ **M** ≤ 8,000  
0 ≤ **Fi** ≤ 100,000  
1 ≤ **Hi** ≤ 100,000  
1 ≤ **Xi** ≤ **N**  
0 ≤ **Yi** ≤ 1,000,000,000  

The sum of **N** across all **T** test cases is no greater than 80,000.  
The sum of **M** across all **T** test cases is no greater than 80,000.

### Explanation of Sample

In the first case, the warehouse is arranged as follows:

![]({{PHOTO_ID:668467847037494}})

If Fred begins in section 1 holding 0 fridges, he can't climb over the wall to
visit section 2, whereas if he's holding 1 fridge, he can place it in section
1 and then climb over. On the other hand, if he begins in section 2, he can
climb over the wall to visit section 1 using the existing fridge, regardless
of whether he's holding any himself.

In the second case, consider the first starting situation, in which Fred
begins in section 3 holding 4 fridges:

![]({{PHOTO_ID:3188801037832284}})

He could begin by placing 3 of his fridges in section 3, and using them to
climb over the wall into section 4 while still holding 1 fridge:

![]({{PHOTO_ID:268184757597716}})

He could then place his remaining fridge in section 4, climb back to section
3, pick up a fridge there, and climb over to section 2 while holding that 1
fridge:

![]({{PHOTO_ID:281442036550128}})

Finally, he could place his final fridge in section 2 and climb over to
section 1:

![]({{PHOTO_ID:657561505101033}})



Sample input:
6
2 4
0 1
1
1 0
1 1
2 0
2 1
4 5
1 2 0 1
3 2 2
3 4
2 0
1 4
4 3
2 6
3 4
10 1 100
20 20
1 25
2 25
3 25
1 29
6 9
6 8 2 0 3 1
5 4 8 4 3
2 3
1 5
5 10
4 7
2 6
6 15
5 2
3 4
4 10
10 10
10 17 9 10 5 13 14 11 0 4
19 16 20 13 6 5 2 4 10
6 11
2 14
4 10
1 22
10 11
7 13
3 11
8 12
2 19
7 9
20 30
17 62 44 11 52 12 20 73 9 13 0 177 41 8 10 52 49 5 27 201
142 73 8 32 5 14 151 47 28 11 13 73 26 9 135 23 6 30 13
7 73
13 32
5 93
6 81
14 48
9 19
1 213
6 73
3 82
15 64
15 47
2 98
8 10
18 0
4 75
6 96
14 48
20 0
4 97
13 32
4 101
14 49
16 6
7 90
8 13
15 48
2 92
1 232
6 79
15 48


Sample output:
Case #1: NYYY
Case #2: YNYNY
Case #3: NYYY
Case #4: NYNNYYNNY
Case #5: NYNNNYNYYN
Case #6: NYYNNNNNYYNYNNNYNYYYYYYYYNNYNN