لدى Саша عدد $n$ من التفاحات ذات الأوزان الصحيحة $w_1,w_2,\ldots,w_n$، وهي موضوعة على الطاولة، ولديها أيضًا سلتان واسعتان.
تختار Саша عددًا صحيحًا $k$ وتنظر في التفاحات التي لا يزيد وزنها على $k$. بعد ذلك يمكنها وضع كل تفاحة وزنها $w_i\le k$ في إحدى السلتين، أو تركها على الطاولة. أما التفاحات التي وزنها $w_i>k$ فتبقى على الطاولة في جميع الأحوال.
نسمي الزوج $(x,y)$ قابلًا للتحقيق بالنسبة إلى $k$ إذا استطاعت Саша وضع بعض التفاحات التي لا يزيد وزنها على $k$ في السلتين بحيث يساوي مجموع أوزان التفاحات في السلة الأولى $x$، ويساوي مجموع أوزان التفاحات في السلة الثانية $y$. ونسمي الزوج $(a,b)$ مثاليًا بالنسبة إلى $k$ إذا كان الزوج $(x,y)$ قابلًا للتحقيق بالنسبة إلى $k$ لكل $x$ و$y$ يحققان $0\le x\le a$ و$0\le y\le b$.
تنظر Саша في $q$ ثلاثيات من الأعداد $k,a,b$، وتريد لكل منها معرفة ما إذا كان الزوج $(a,b)$ مثاليًا بالنسبة إلى $k$.
الإدخال
يحتوي السطر الأول على عددين صحيحين $n$ و$q$، هما عدد التفاحات التي تملكها Саша وعدد الاستعلامات التي يجب معالجتها ($1\le n,q\le300\,000$).
يحتوي السطر الثاني على $n$ أعداد صحيحة $w_1,w_2,\ldots,w_n$، وهي أوزان التفاحات التي تملكها Саша ($1\le w_i\le10^{12}$).
يحتوي السطر الثالث على عدد صحيح $z$ يستخدم لتكوين الاستعلامات التي يجب الإجابة عنها ($0\le z\le10^6$).
تحتوي الأسطر $q$ التالية على أوصاف الاستعلامات. ترقم الاستعلامات من $1$ إلى $q$. يحتوي كل سطر على ثلاثة أعداد صحيحة $j,c,d$ ($0\le j,c,d\le10^{18}$). يتكون الاستعلام من أعداد هذا السطر وفق القواعد التالية. نحسب $v$ بوصفه مجموع أرقام الاستعلامات السابقة للاستعلام الحالي التي كان الزوج $(a,b)$ المحدد فيها مثاليًا بالنسبة إلى $k$. عندئذ تكون قيم الاستعلام الحالي $k=j-v\cdot z$ و$a=c-v\cdot z$ و$b=d-v\cdot z$. يضمن أن $k,a,b\ge0$.
لاحظ أنه عندما يكون $z=0$ (وهو الحال في معظم المهام الفرعية)، تساوي قيم $k,a,b$ القيم $j,c,d$ على الترتيب. أي إن معاملات الاستعلام لا تعتمد على إجابات الاستعلامات السابقة، وترد صراحة في بيانات الإدخال.
الإخراج
لكل استعلام، اطبع Yes إذا كان الزوج $(a,b)$ في ذلك الاستعلام مثاليًا بالنسبة إلى $k$، وإلا فاطبع No.
المهام الفرعية
| المهمة الفرعية | النقاط | قيود إضافية على $n,q$ | قيود إضافية على $a,b$ | قيود إضافية على $k$ | قيود إضافية على $z$ | المهام الفرعية المطلوبة |
|---|---|---|---|---|---|---|
| 1 | 9 | $n,q\le10$ | $z=0$ | |||
| 2 | 6 | $n\le100$ | $a\le100\,000,b=0$ | $k=10^{18}$ | $z=0$ | |
| 3 | 3 | $b=0$ | $k=10^{18}$ | $z=0$ | 2 | |
| 4 | 6 | $n,q\le100$ | $a,b\le300$ | $k=10^{18}$ | $z=0$ | |
| 5 | 6 | $n\le100$ | $a,b\le300$ | $k=10^{18}$ | $z=0$ | 4 |
| 6 | 2 | $n\le1500$ | $a,b\le1500$ | $k=10^{18}$ | $z=0$ | 4–5 |
| 7 | 6 | $n\le5000$ | $a,b\le5000$ | $k=10^{18}$ | $z=0$ | 4–6 |
| 8 | 2 | $a,b\le200\,000$ | $k=10^{18}$ | $z=0$ | 2, 4–7 | |
| 9 | 9 | $k=10^{18}$ | $z=0$ | 2–8 | ||
| 10 | 3 | $b=0$ | $z=0$ | 2–3 | ||
| 11 | 6 | $n,q\le100$ | $a,b\le300$ | $z=0$ | 4 | |
| 12 | 6 | $n\le100$ | $a,b\le300$ | $z=0$ | 4–5, 11 | |
| 13 | 2 | $n,q\le1500$ | $a,b\le1500$ | $z=0$ | 4, 11 | |
| 14 | 2 | $n\le1500$ | $a,b\le1500$ | $z=0$ | 4–6, 11-13 | |
| 15 | 6 | $n\le5000$ | $a,b\le5000$ | $z=0$ | 4–7, 11-14 | |
| 16 | 2 | $a,b\le200\,000$ | $z=0$ | 4–8, 11–15 | ||
| 17 | 6 | $z=0$ | 1–16 | |||
| 18 | 18 | أمثلة, 1–17 |
أمثلة
الإدخال 1
8 5 17 1 3 2 100 5 6 1 0 6 15 3 9 4 4 5 15 3 17 34 1 16 33 2
الإخراج 1
Yes No No Yes No
الإدخال 2
8 5 17 1 3 2 100 5 6 1 1 6 15 3 10 5 5 6 16 4 18 35 2 21 38 7
الإخراج 2
Yes No No Yes No