لتظهر الأبقار روح العطلة تريد رسم صورة! تمثلها شبكة $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