Problem I
Terrain Monitoring

The “Great Gravel Mountain Range” is a popular hiking destination. It consists of a series of gravel mountains which just so happen to form a perfectly straight line running north to south. Unfortunately, due to the loose nature of the underlying gravel, the mountains are prone to landslides.

A landslide will affect a contiguous subrange of the mountains causing it to level out a bit. More precisely, the tallest mountain (with the height $M$) and the smallest mountain (with height $m$) in the subrange will even out. The tallest mountain will end up with a height equal to their average rounded up to the nearest integer (that is, $\left\lceil (M + m) / 2\right\rceil $). The smallest mountain will end up with a height equal to their average rounded down to the nearest integer (that is, $\left\lfloor (M + m) / 2\right\rfloor $). None of the other mountains will be affected. In the case that there is more than one mountain with maximum height, the southernmost mountain will be affected and in the case that there is more than one mountain of minimum height, the northernmost mountain will be affected.

In order to keep hikers safe, you’ve been stationed in a booth near the entrance to the range so that before the hikers enter, you can tell them if the region they plan to visit is safe or not. A series of sensors have been placed around the mountain range which will inform you of any landslides that occur. You figure that subranges with higher peaks and lower valleys are more likely have a landslide so you predict a subrange to be safe to enter if the difference between the highest and lowest mountain in the subrange $(M - m)$ is strictly less than the safety threshold $t$.

Given the initial heights of the mountains in the range, the safety threshold, and updates about landslides, can you help each of the hikers stay safe?

Input

The first line of input contains a single integer $n$ $(2 \leq n \leq 5 \cdot 10^5)$ the number of mountains in the range. The next line contains $n$ integers $h_1, h_2, \ldots , h_n$ $(0 \leq h_i \leq 10^6)$ the initial heights of the mountains in the range from north to south. The following line contains two integers $q$ $(1 \leq q \leq 10^5)$ and $t$ $(1 \leq t \leq 10^6)$ the number of events and the safety threshold respectively. The next $q$ lines each contain a single character $c$ ($c \in \{ \texttt{L}, \texttt{S}\} $) the event type, and two integers $a$ $(1\leq a < n)$, and $b$ $(a < b \leq n)$ the starting and ending indices of the subrange relating to the event. The types of events are as follows:

• L: A landslide has just occurred in the subrange $[a, b]$ (including both the $a$th and $b$th mountains)

• S: A hiker has just arrived and has inquired about the safety of subrange $[a, b]$ (including both the $a$th and $b$th mountains)

It is guaranteed that there will be at least one safety check.

Output

For each safety check, print one line containing SAFE if the subrange is considered safe for the hiker to enter, or DANGER otherwise.

5
10 1 2 3 4
3 5
S 1 5
L 1 3
S 1 5

DANGER
SAFE

4
1 1 5 5
4 2
S 1 2
S 3 4
L 2 3
S 3 4

SAFE
SAFE
DANGER