Math jam

Daria and Mary play a game with towers made of sandwiches of two types: apricot and raspberry. The game rules are as follows:

1. Players alternate turns with Daria going first; a player unable to make a valid move loses.

2. On their turn, a player removes one sandwich of their type (apricot is Daria's type and raspberry is Mary's) from any tower. They can take it from any position.

3. But if a player tries to remove a sandwich that supports the tower (its base, and it must be a sandwich of their type), they must eat the entire tower instead (even if there are sandwiches of another players in this tower).

You are given $n$ towers and $q$ queries of the form $x_i,y_i$. The task is to determine who is going to win if the game was played on the towers whose indexes are from segment $[x_i,y_i]$.

Input

The first line contains two integers $n(1\le n\le 3\cdot 10^5)$ and $q(1\le q\le 10^6)$ — the number of towers, and the number of queries.

The next $n$ lines describe the towers in format $t_i$ $a_i$ $r_i$ ($0\le a_i,r_i<10^5$, $t_i\in \{A,R\}$). $t_i=A$ if the base of $i$-th tower is apricot sandwich. $t_i=R$ if the base of $i$-th tower is raspberry sandwich. $a_i$ indicates the total number of apricot sandwiches in $i$-th tower. $r_i$ indicates the total number of raspberry sandwiches in $i$-th tower. If $t_i=A$ then $a_i>0$. If $t_i=R$ then $r_i>0$.

The next $q$ lines contain a pair of integers $x_i,y_i(1\le x_i\le y_i\le n)$ — the parameters of the $i$-th query.

Output

On the $i$-th line output «Daria» if Daria wins when the game is played on towers from $i$-th query. Otherwise, output «Mary».

Examples

Note

In the second query, we have such towers: $[RA,A]$ (starting from the base). On the first move, Daria has two options:

1. If Daria takes the sandwich from the first tower making the towers $[R,A]$, then Mary is forced to take her only sandwich to make towers $[A]$. Then Daria takes the last sandwich and after Mary can't make a move, so Daria wins;

2. If Daria takes the sandwich from the second tower making the towers $[RA]$, then Mary is forced to take her only sandwich (she takes a sandwich from the base, therefore eats a whole tower). After that there are no towers left, Daria can't make a valid move, therefore Mary wins.

Daria can win if she does the first described move and therefore she wins in this case.

Scoring

1. ($10$ points): $y_i-x_i\le 1$;

2. ($10$ points): $y_i-x_i\le 2$;

3. ($10$ points): $a_i=r_i$;

4. ($10$ points): $a_i,r_i\le 2$;

5. ($60$ points): $n,q,a_i,r_i\le 5000$;

6. ($40$ points): $n=q,x_i=1,y_i=i$.

7. ($70$ points): $a_i,r_i<30$;

8. ($50$ points): $n,q\le 10^5$;

9. ($40$ points): no additional constraints;