Farmer John הרחיב לאחרונה את החווה, ומנקודת מבט הפרות היא כעת למעשה אינסופית! הן רואות את המרעה כרשת דו־ממדית אינסופית של תאים ריבועיים מלאי עשב טעים (כמו לוח שחמט אינסופי). כל אחת מ־$N$ הפרות ($1\le N\le 50$) מתחילה בתא אחר; חלקן פונות צפונה וחלקן מזרחה.

בכל שעה כל פרה מבצעת אחת מהפעולות הבאות:

• נעצרת אם העשב בתא שלה כבר נאכל בידי פרה אחרת.
• אוכלת את כל העשב בתא ומתקדמת תא אחד בכיוון שאליו היא פונה.

עם הזמן כל פרה מותירה מאחוריה ״תלם״ עקר של תאים ריקים.

אם שתי פרות נכנסות לאותו תא עם עשב באותה תנועה, הן חולקות אותו וממשיכות בכיווניהן בשעה הבאה.

מצאו את כמות העשב שכל פרה אוכלת. חלקן אינן נעצרות לעולם ואוכלות כמות אינסופית.

קלט

השורה הראשונה מכילה $N$. כל אחת מ־$N$ השורות הבאות מתארת את התחלת הפרה בתו N (צפון) או E (מזרח) ושני מספרים שלמים לא־שליליים $x$ ו־$y$ ($0\le x\le 10^9$, $0\le y\le 10^9$), קואורדינטות התא. כל קואורדינטות $x$ שונות, וכך גם כל קואורדינטות $y$.

להבהרת הכיוונים, מ־$(x,y)$ תנועה צפונה מגיעה ל־$(x,y+1)$ ותנועה מזרחה ל־$(x+1, y)$.

פלט

הדפיסו $N$ שורות. שורה $i$ נותנת את מספר תאי העשב שאוכלת הפרה ה־$i$ בקלט. לכמות אינסופית הדפיסו Infinity עבור אותה פרה.

דוגמאות

קלט 1

6
E 3 5
N 5 3
E 4 6
E 10 4
N 11 2
N 8 1

פלט 1

5
3
Infinity
Infinity
2
5

תת־משימות

• במקרי הבדיקה $2$ עד $5$ כל הקואורדינטות לכל היותר $100$.
• במקרי הבדיקה $6$ עד $10$ אין מגבלות נוספות.

מחבר הבעיה: Brian Dean