لدى Little L شبكة مثلثية منتظمة، حيث كل خط في الشبكة هو قطعة مستقيمة تصل بين نقاط التقسيم الـ $n$ المتناظرة للأضلاع المتجاورة. تقسم خطوط الشبكة هذه المثلث المتساوي الأضلاع إلى عدة مثلثات متساوية أضلاع أصغر ومتطابقة.
لكل نقطة تقاطع لخطوط الشبكة في الشكل، نمثلها بالإحداثيين $(x, y)$. يتراوح الإحداثي $x$ من الأعلى إلى الأسفل بين $1$ و $n + 1$. يمثل $x = 1$ النقطة العليا، بينما يمثل $x = n + 1$ الخط السفلي. بالنسبة للصف ذي الترتيب $i$، تتراوح الإحداثيات $y$ لنقاط الشبكة من اليسار إلى اليمين بين $1$ و $i$.
يوجد في الشبكة المثلثية عدة مثلثات متساوية الأضلاع، قد تكون موجهة للأعلى (معتدلة) أو للأسفل (مقلوبة). لكل اتجاه للمثلث، نمثله بثلاثة أعداد $x, y, d$. هنا، $(x, y)$ يمثل إحداثيات الرأس المقابل لضلع المثلث الموازي للخط السفلي للشبكة، و $d$ يمثل طول ضلعه (طول القطعة المستقيمة).
على سبيل المثال، في الشكل أدناه، المثلث المنتظم الأزرق هو مثلث معتدل بمعاملات $(x, y, d) = (4, 2, 3)$. والمثلث المنتظم الأصفر هو مثلث مقلوب بمعاملات $(x, y, d) = (6, 3, 2)$.

الآن، لكل خلية مثلثية منتظمة صغيرة واحدية (مثلث متساوي الأضلاع طول ضلعه $1$، بغض النظر عن اتجاهه)، يوجد عدد مكتوب عليها. في البداية، جميع الأعداد على الشبكة تساوي $0$. سيقوم Little L بإجراء العمليات التالية:
- اختيار مثلث منتظم وإضافة $w$ إلى جميع الأعداد الموجودة في خلايا الشبكة داخله.
- اختيار مثلث منتظم والاستعلام عن مجموع جميع الأعداد الموجودة في خلايا الشبكة داخله.
يأمل أن تتمكن من حساب الإجابة لكل عملية استعلام. وبما أن Little L لا يحب الأعداد الكبيرة، فما عليك سوى طباعة نتيجة الإجابة بباقي القسمة على $2^{32}$.
الإدخال
يحتوي السطر الأول من الإدخال على عددين صحيحين $n, q$ ($2 \le n \le 10^5, 1 \le q \le 10^5$).
تمثل الأسطر الـ $q$ التالية عملية واحدة في كل سطر.
يبدأ كل سطر بخمسة أعداد $opt, type, x, y, d$ ($opt \in \{1, 2\}, type \in \{0, 1\}, 1 \le x \le n + 1, 1 \le y \le x, 1 \le d \le n$). يمثل $opt$ نوع العملية، حيث $opt = 1$ عملية تعديل، و $opt = 2$ عملية استعلام. يشير $type$ إلى نوع المثلث في هذه العملية، حيث $type = 0$ للمثلث المعتدل، و $type = 1$ للمثلث المقلوب. وتصف $x, y, d$ هذا المثلث. إذا كان $opt = 1$، فهناك عدد إضافي $w$ ($0 \le w < 2^{32}$) يشير إلى العدد المضاف خلال عملية التعديل هذه.
من المضمون أن جميع المثلثات المدخلة لها مساحة غير صفرية وهي مثلثات صالحة محتواة بالكامل داخل المثلث الأكبر.
الإخراج
لكل استعلام فيه $opt = 2$، اطبع عدداً واحداً في سطر جديد يمثل المجموع داخل المنطقة بباقي القسمة على $2^{32}$.
أمثلة
الإدخال 1
5 5 1 0 3 3 2 2 1 1 6 4 2 3 2 0 1 1 5 2 0 3 2 3 2 1 5 3 2
الإخراج 1
20 11 3
الإدخال 2
10 10 1 0 1 1 5 2 1 1 3 2 1 6 1 1 6 4 2 1 2 0 10 3 1 2 1 5 2 1 2 1 6 4 2 1 0 7 7 1 7 1 1 9 3 1 3 1 0 9 5 2 4 2 0 6 1 2
الإخراج 2
0 2 12 0