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