Bessie לכודה במבוך משולש של $N$ שורות, $1 \le N \le 1,000,000$. להלן שלוש שורות.

שורה $i$ מכילה $2*i-1$ משולשים, משמאל $(i,1)$, $(i,2)$ וכו׳.

אפשר לעבור למשולש בעל צלע משותפת, לרוב שלושה. מ־$(3,3)$ אל $(3,2)$, $(3,4)$, $(4,4)$. כל מעבר דקה.

FJ יודע שהיא לכודה ועוקב אחרי iPhone: מסע היציאה מתחיל ב־($Si,Sj$). אהבתו בלי גבול והוא רוצה חזרה מהירה ביותר.

יש $M$ יציאות מפוזרות, $1 \le M \le 10,000$, כל אחת מאפשרת בריחה. אחרי כניסה למשולש יציאה צריך רק עוד דקה לצאת מהמבוך.

מצאו את הזמן המזערי $T$ דקות ואת היציאה המיטבית $(OUTi, OUTj)$. בשוויון $T$ בחרו שורה קטנה ביותר, ובשורה שווה עמודה קטנה יותר.

קלט

• שורה $1$: שלמים $N$, $M$ מופרדי רווח.

• שורה $2$: שלמים $Si$, $Sj$ מופרדי רווח.

• שורות $3..M+2$: שורה $i+2$, שני שלמים מופרדי רווח $Ei$, $Ej$, משולש יציאה $i$.

פלט

• שורה $1$: שלמים $OUTi$, $OUTj$ מופרדי רווח.

• שורה $2$: שלם אחד $T$.

דוגמאות

קלט 1

4 2
2 1
3 5
4 4

פלט 1

4 4
4

מחבר הבעיה: Ye Wang, 2009