Broken Time Machine
By Francisco Elio Parente Arcos Filho, UEA 
Brazil
By Francisco Elio Parente Arcos Filho, UEA Brazil
Farcos has a time machine, and it can travel to the future as well as to the past, but it is broken and can not make two consecutive jumps of the same type, that is, it can not make two consecutive jumps for the future, nor two consecutive jumps to the past. Additionally to this, it can not travel an arbitrary amount of years in time. The length in years of a jump into the future is determined by the buttons in panel \(A\) where pressing a button \(X\) means making a jump of \(X\) years to the future. In the same way the sizes of the jump to the past are determined by the buttons in panel \(B\).
Despite having two panels, the machine was initially designed to have only one panel. Where all buttons would be sorted non-descending from left to right. But this idea was soon discarded since the buttons of at least one of the two types (\(A\) and \(B\)) were never all together, thus forming an aesthetic pattern not very pleasant.
Your task is, given the value of the buttons that are in panel \(A\) and \(B\), and the current year that Farcos is in, answer if he can travel for a certain period of time.
The first jump of the machine is always for the future.
The first line of the input consists of two integers N (2 ≤ N ≤ 105) and M (2 ≤ M ≤ 105) respectively representing the number of buttons in panel \(A\) and panel \(B\). The second line of the input consists of N integers Ai (1 ≤ Ai ≤ 109) representing the buttons in panel \(A\). The third line of the input consists of integers M integers Bi (1 ≤ Bi ≤ 109) representing the buttons in panel \(B\). The fourth line of the input consists of an integer Q (1 ≤ Q ≤ 105) representing the number of queries about possible trips. Each of the following Q lines contains two integers S (1 ≤ S ≤ 109) and T (1 ≤ T ≤ 109) representing respectively the starting year of the machine and the desired year of arrival. Each query is independent of the other.
The output consists of one line per query. Each line contains "S" (without quotation marks) if its travel is possible or "N" (without quotation marks), otherwise.
| Input Samples | Output Samples |
|
2 2 2 8 6 11 3 2019 2021 2019 2015 2019 2010 |
S S S |
|
3 2 1 7 16 4 13 4 2019 2021 2019 2020 1994 2019 2019 1994 |
N S S N |