כדי להפגין את רוח החג, הפרות רוצות לצייר! התמונה היא רשת $R$ $\times$ $C$ $(1 \le R \le 50,000; 1 \le C \le 15)$ של ריבועי יחידה, כל אחד0 או1. השורות ממוספרות $1,\ldots,R$ והעמודות $1,\ldots,C$.
בגלל קוצר הזמן ביקשו עזרה מהשכנים מצפון לגבול. בהנחייתו האדיבה של האייל Canmuu בנו מכונה שמשליכה דליי צבע שלמים! בתחילה הרשת כולה0; המכונה צובעת מלבן בצבע0 או1. Canmuu מציע $Q$ פעולות $(1 \le Q \le 10,000)$; פעולה $i$ כוללת חמישה שלמים $R1_{i}$, $R2_{i}$, $C1_{i}$, $C2_{i}$, $X_{i}$ $(1 \le R1_i \le R2_i \le R; 1 \le C1_i \le C2_i \le C; 0 \le X_{i} \le 1)$ וצובעת ב־$X_{i}$ כל תא ששורתו מ־$R1_{i}$ עד $R2_{i}$ ועמודתו מ־$C1_{i}$ עד $C2_{i}$, כולל הקצוות.
כך קל לטעות, ולכן Canmuu מבקש לקבוע אחרי כל פעולה כמה ריבועים הם בצבע הנכון.
מגבלת זיכרון:64 MB
מגבלת זמן:1.5 שניות
קלט
- שורה1: שלושה שלמים מופרדים ברווחים $R$, $C$, $Q$.
- שורות $2,\ldots,R+1$: שורה $i+1$ מכילה $C$ תווים '0' או '1', המייצגים את השורה $i$.
- שורות $R+2,\ldots,R+Q+1$: שורה $R+i+1$ מכילה חמישה שלמים ברווחים לפעולה: $R1_{i}$, $R2_{i}$, $C1_{i}$, $C2_{i}$, $X_{i}$.
פלט
- שורות $1,\ldots,Q$: בשורה $i+1$ הדפיסו שלם יחיד, מספר התאים המתאימים אחרי פעולה $i$.
דוגמאות
קלט 1
17 15 10 111111101111111 111111000111111 111110000011111 111100000001111 111000000000111 111100000001111 111000000000111 110000000000011 111000000000111 110000000000011 100000000000001 110000000000011 100000000000001 000000000000000 111111000111111 111111000111111 111111000111111 5 8 2 14 1 8 17 3 7 1 4 5 10 15 0 7 16 12 14 1 2 17 13 14 0 2 6 2 3 1 13 14 4 8 1 3 6 6 7 1 1 16 10 11 0 7 16 10 10 0
פלט 1
113 94 95 91 87 93 91 87 93 93
הערה
הפרות רוצות לצייר עץ של חג.
אחרי הפעולה הראשונה הרשת היא:
000000000000000 000000000000000 000000000000000 000000000000000 011111111111110 011111111111110 011111111111110 011111111111110 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000
113 ריבועים תואמים לריבועים המקבילים בעץ; מסומנים למטה 'x' (הביטים האחרים מוצגים כפי שהם אחרי זריקת הצבע הראשונה):
0000000x0000000 000000xxx000000 00000xxxxx00000 0000xxxxxxx0000 0xx111111111xx0 0xxx1111111xxx0 0xx111111111xx0 0x11111111111x0 000xxxxxxxxx000 00xxxxxxxxxxx00 0xxxxxxxxxxxxx0 00xxxxxxxxxxx00 0xxxxxxxxxxxxx0 xxxxxxxxxxxxxxx 000000xxx000000 000000xxx000000 000000xxx000000
מחברי הבעיה: Brian Hamrick ו־Neal Wu, 2008