Математична гра

Дар'я та Марія грають у гру з вежами, зробленими з сендвічів двох типів: абрикосовий та малиновий. Правила гри такі:

1. Гравці по черзі ходять, причому Дар'я ходить першою; гравець, який не може зробити валідний хід, програє.

2. У свій хід гравець знімає один сендвіч свого типу (абрикосовий - тип Дар'ї, малиновий - тип Марії) з будь-якої вежі. Він може взяти його з будь-якої позиції.

3. Але якщо гравець намагається зняти сендвіч, який підтримує вежу (її основу, і це повинен бути сендвіч його типу), він повинен з'їсти всю вежу замість цього (навіть якщо в цій вежі є сендвічі іншого гравця).

Вам дано $n$ веж і $q$ запитів у формі $x_i,y_i$. Завдання полягає в тому, щоб визначити, хто виграє, якщо гра буде зіграна на вежах, індекси яких знаходяться в відрізку $[x_i,y_i]$.

Вхідні дані

Перший рядок містить два цілі числа $n(1\le n\le 3\cdot 10^5)$ та $q(1\le q\le 10^6)$ — кількість веж та кількість запитів.

Наступні $n$ рядків описують вежі у форматі $t_i$ $a_i$ $r_i$ ($0\le a_i,r_i<10^5$, $t_i\in \{A,R\}$). $t_i=A$, якщо основа $i$-ї вежі - абрикосовий сендвіч. $t_i=R$, якщо основа $i$-ї вежі - малиновий сендвіч. $a_i$ вказує загальну кількість абрикосових сендвічів у $i$-й вежі. $r_i$ вказує загальну кількість малинових сендвічів у $i$-й вежі. Якщо $t_i=A$, то $a_i>0$. Якщо $t_i=R$, то $r_i>0$.

Наступні $q$ рядків містять пару цілих чисел $x_i,y_i(1\le x_i\le y_i\le n)$ — параметри $i$-го запиту.

Вихідні дані

У $i$-му рядку виведіть «Daria», якщо Дар'я виграє, коли гра грається на вежах з $i$-го запиту. В іншому випадку виведіть «Mary».

Приклади

Примітка

У другому запиті у нас є такі вежі: $[RA,A]$ (починаючи з основи). На першому ході у Дар'ї є два варіанти:

1. Якщо Дар'я забирає сендвіч з першої вежі, роблячи вежі $[R,A]$, тоді Марія змушена взяти свій єдиний сендвіч, щоб зробити вежі $[A]$. Тоді Дар'я забирає останній сендвіч, і після цього Марія не може зробити хід, тому Дар'я виграє;

2. Якщо Дар'я забирає сендвіч з другої вежі, роблячи вежі $[RA]$, тоді Марія змушена взяти свій єдиний сендвіч (вона забирає сендвіч з основи, отже, з'їдає всю вежу). Після цього веж більше не залишилося, Дар'я не може зробити валідний хід, отже, виграє Марія.

Дар'я може виграти, якщо вона зробить перший описаний хід, і тому вона виграє в цьому випадку.

Оцінювання

1. ($10$ балів): $y_i-x_i\le 1$;

2. ($10$ балів): $y_i-x_i\le 2$;

3. ($10$ балів): $a_i=r_i$;

4. ($10$ балів): $a_i,r_i\le 2$;

5. ($60$ балів): $n,q,a_i,r_i\le 5000$;

6. ($40$ балів): $n=q,x_i=1,y_i=i$.

7. ($70$ балів): $a_i,r_i<30$;

8. ($50$ балів): $n,q\le 10^5$;

9. ($40$ балів): без додаткових обмежень;