小葱 ו-小绪 הם חברים טובים. מאז ש-小葱 השיג 1UR2SR בהגרלה של 11 פריטים, 小绪 חשב שמזלו של 小葱 טוב במיוחד, ולכן הציב לו בעיה כדי לבחון את מזלו.

תחילה צייר 小绪 על המישור $N$ נקודות, $P_1,P_2,\ldots,P_N$. הוא חיבר אותן לפי הסדר, כלומר חיבר את $(P_1,P_2),(P_2,P_3),\ldots,(P_{N-1},P_N)$, וקיבל $N-1$ קטעים.

לאחר מכן, בכל פעם צייר 小绪 ישר על המישור ושאל את 小葱 כמה קטעים הישר חותך. בפרט, חיתוך בקצה של קטע נחשב לחיתוך, וגם מצב שבו הישר מכיל את הקטע כולו נחשב לחיתוך.

בעיה כזאת כמובן אינה מקשה על 小葱: בזכות מזלו הוא יכול לתת את התשובה הנכונה בעזרת האינטואיציה בלבד.

小绪 רצה לבדוק עד כמה טוב מזלו של 小葱, ולכן הקשה את הבעיה:

נוסף על השאילתות, מפעם לפעם 小绪 יכניס נקודה חדשה $P$ בין $P_i$ ל-$P_{i+1}$, ואז ימספר מחדש את כל הנקודות לפי הסדר. כלומר, האינדקסים של הנקודות שאחרי $P_i$ יגדלו, והנקודה $P$ תהיה $P_{i+1}$ החדשה. בפרט, אפשר להכניס את $P$ גם לפני הנקודה הראשונה או אחרי הנקודה האחרונה.

小葱, שמזלו מצוין, עדיין הצליח לענות בקלות, ולכן 小绪 הקשה עוד יותר:

לאחר כל הכנסה או שאילתה, 小绪 שמר את כל הקטעים במצב שלאחר הפעולה, וקרא לכך גרסה היסטורית. גרסה היסטורית $T$ היא הגרסה שהתקבלה לאחר הפעולה ה-$T$.

פעולת הכנסת נקודה חדשה שונתה: כעת מכניסים נקודה $P$ על בסיס גרסה היסטורית כלשהי $T$, ומקבלים גרסה היסטורית חדשה. לאחר שאילתה, הגרסה ההיסטורית החדשה היא הגרסה ההיסטורית $T$ שעליה נשאלה השאילתה.

השאילתות של 小绪 הן כעת: עבור גרסה היסטורית $T$ וישר נתון, כמה קטעים חותך הישר?

אף שמזלו של 小葱 טוב, מול בעיה כזאת גם הוא חסר אונים. לכן הוא פנה אליכם, משתתפי CTSC, וביקש שתעזרו לו לפתור אותה.

קלט

קובץ הקלט הוא shallot.in.

השורה הראשונה מכילה שני מספרים שלמים $N,M,C$, המציינים את מספר הנקודות ההתחלתי, מספר הפעולות הכולל והאם הנתונים מוצפנים. אם $C=1$, הנתונים מוצפנים: הערכים $X_0,Y_0,X,Y$ בכל שאילתה והערכים $X,Y$ בכל הכנסת נקודה הם נתונים מוצפנים. יש לבצע עליהם XOR עם $\mathit{last\_ans}$ כדי לקבל את הנתונים הנכונים, כאשר $\mathit{last\_ans}$ הוא התשובה לשאילתה הקודמת, וערכו ההתחלתי הוא $\mathit{last\_ans}=0$.

לאחר מכן יש $N$ שורות, שכל אחת מכילה שני שלמים. שני המספרים בשורה $i$ הם הקואורדינטה האופקית והקואורדינטה האנכית של $P_i$.

לאחר מכן יש $M$ שורות המתארות את $M$ הפעולות של 小绪. התוצאה לאחר הפעולה בשורה $i$ (המספור מתחיל ב-$1$) היא הגרסה ההיסטורית $i$.

בכל פעולה מופיעה תחילה אות המציינת את סוג הפעולה הנוכחית של 小绪.

אם האות היא H, זוהי שאילתה: אחריה חמישה שלמים $T,X_0,Y_0,X,Y$. הם מציינים שבגרסה ההיסטורית $T$, 小绪 נותן ישר העובר דרך $(X_0,Y_0)$ וכיוונו $(X,Y)$; 小葱 צריך לענות כמה קטעים הוא חותך.

אם האות היא Z, זוהי הכנסת נקודה. אחריה ארבעה מספרים $T,i,X,Y$, המציינים שעל בסיס הגרסה ההיסטורית $T$, 小绪 מכניס נקודה שקואורדינטותיה $(X,Y)$ אחרי $P_i$. בפרט, אם $i=0$, הנקודה מוכנסת לפני $P_1$.

פלט

בקובץ הפלט shallot.out יש להדפיס לכל שאילתה שורה ובה שלם אחד: התשובה הנכונה שעל 小葱 לתת.

דוגמאות

קלט 1

2 3 0
0 0
1 1
H 0 1 0 -1 1
H 1 0 1 1 1
H 2 -1 -1 1 1

פלט 1

1
0
1

הערה

בשאילתה השלישית הישר מכיל את הקטע כולו, וגם מצב זה נחשב אצל 小绪 לחיתוך.

קלט 2

2 3 0
0 0
2 2
Z 0 2 0 2
H 0 0 1 1 1
H 1 0 1 1 1

פלט 2

0
2

דוגמה 3

ראו את shallot/shallot.in ואת shallot/shallot.ans בתיקיית המתחרה.

מגבלות

מובטח שהערך $T$ בכל שאילתה אינו גדול ממספר הפעולות הנוכחי, וכל נתוני הקלט הם שלמים.

יש ארבעה סוגים מיוחדים של נתונים, הזרים זה לזה בזוגות:

1. עבור $15\%$ מהנתונים, מובטח $1\le N,M\le1000$.
2. עבור $15\%$ מהנתונים, מובטח שבפעולה ה-$i$ מתקיים $T=i-1$.
3. עבור $15\%$ מהנתונים, מובטח $C=0$ ואין פעולות שינוי.
4. עבור $15\%$ מהנתונים, בכל הכנסת נקודה מובטח $Y=0$ (בנתונים מוצפנים הכוונה ל-$Y$ לאחר הפענוח), כלומר הישר הנתון מקביל לציר $x$.

עבור הנתונים הנזכרים לעיל מובטח גם $1\le N,M\le5\times10^4$.

עבור $100\%$ מהנתונים, מובטח $1\le N,M\le10^5$, כל הקואורדינטות הן בתחום $[-10^8,10^8]$, וסכום התשובות לכל השאילתות בכל קבוצת נתונים אינו עולה על $10^6$. מספר פעולות ההכנסה אינו עולה על $5\times10^4$. שימו לב שהקטעים עשויים לחתוך זה את זה.