[Maxim6m0cj]

Perica and Jovica are collecting piles of blueberries. There are N piles of blueberries lined up. Perica is collecting the piles from the beginning of the line, while Jovica is collecting them from the end of the line. After collecting all of the blueberry piles, both of them count their own blueberries.

You are given Q queries. Every query consists of one integer K, and you have to answer if it is possible that both Perica and Jovica end up with more than K blueberries.

INPUT:
The first line of the standard input has two integers N and Q (1 <= N <= 100.000, 1 <= Q <= 1.000.000), number of piles and number of queries. There are N integers from the interval [1, 1.000.000] in the second line, representing the number of blueberries in each of the N piles. Each of the next Q lines contains an integer K (1 <= K <= 1.000.000.000). OUTPUT: Print Q lines - one answer for each of the Q queries. Every line has to containt one character: d - if it is possible that both of them collect more than K blueberries, or n - if it is not possible that both of them collect more than K blueberries.

Input:
4 3
3 8 5 6
7
14
11

Output:
d
n
n

Input:
4 1
8 1 2 2
4

Output:
d

Explanation: If Perica takes the first pile of blueberries (8), and Jovica takes the remaining three piles (2 + 2 + 1 = 5), both of them will end up with more than 4 blueberries.