ל־Саша יש $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$ המקיימים $0\le x\le a$ ו־$0\le y\le b$, הזוג $(x,y)$ הוא בר־השגה עבור $k$.
Саша מתבוננת ב־$q$ שלשות מספרים $k,a,b$, ורוצה לדעת עבור כל אחת מהן אם הזוג $(a,b)$ מושלם עבור $k$.
קלט
בשורה הראשונה נתונים שני מספרים שלמים $n$ ו־$q$: מספר התפוחים שיש ל־Саша ומספר השאילתות שעליכם לעבד ($1\le n,q\le 300\,000$).
בשורה השנייה נתונים $n$ מספרים שלמים $w_1,w_2,\ldots,w_n$, משקלי התפוחים שיש ל־Саша ($1\le w_i\le 10^{12}$).
בשורה השלישית נתון מספר שלם $z$, המשמש ליצירת השאילתות שעליהן יש לענות ($0\le z\le 10^6$).
ב־$q$ השורות הבאות נתונים תיאורי השאילתות. השאילתות ממוספרות מ־$1$ עד $q$. כל שורה מכילה שלושה מספרים שלמים $j,c,d$ ($0\le j,c,d\le 10^{18}$). השאילתה נוצרת מהמספרים בשורה על פי הכללים הבאים. נחשב את $v$ כסכום המספרים של השאילתות הקודמות שבהן הזוג $(a,b)$ היה מושלם עבור $k$. אז בשאילתה הנוכחית $k=j-v\cdot z$; $a=c-v\cdot z$; $b=d-v\cdot z$. מובטח כי $k,a,b\ge 0$.
שימו לב שכאשר $z=0$ (כפי שקורה ברוב תתי־המשימות), הערכים $k,a,b$ שווים בהתאמה ל־$j,c,d$. כלומר, פרמטרי השאילתה אינם תלויים בתשובות לשאילתות קודמות, ונתונים במפורש בקלט.
פלט
עבור כל שאילתה הדפיסו Yes אם הזוג $(a,b)$ שבשאילתה מושלם עבור $k$, ואחרת הדפיסו No.
תתי־משימות
| תת־משימה | נקודות | מגבלות נוספות: $n,q$ | מגבלות נוספות: $a,b$ | מגבלות נוספות: $k$ | מגבלות נוספות: $z$ | תתי־משימות נדרשות |
|---|---|---|---|---|---|---|
| 1 | 9 | $n,q\le 10$ | $z=0$ | |||
| 2 | 6 | $n\le 100$ | $a\le 100\,000$, $b=0$ | $k=10^{18}$ | $z=0$ | |
| 3 | 3 | $b=0$ | $k=10^{18}$ | $z=0$ | 2 | |
| 4 | 6 | $n,q\le 100$ | $a,b\le 300$ | $k=10^{18}$ | $z=0$ | |
| 5 | 6 | $n\le 100$ | $a,b\le 300$ | $k=10^{18}$ | $z=0$ | 4 |
| 6 | 2 | $n\le 1\,500$ | $a,b\le 1\,500$ | $k=10^{18}$ | $z=0$ | 4–5 |
| 7 | 6 | $n\le 5\,000$ | $a,b\le 5\,000$ | $k=10^{18}$ | $z=0$ | 4–6 |
| 8 | 2 | $a,b\le 200\,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\le 100$ | $a,b\le 300$ | $z=0$ | 4 | |
| 12 | 6 | $n\le 100$ | $a,b\le 300$ | $z=0$ | 4–5, 11 | |
| 13 | 2 | $n,q\le 1\,500$ | $a,b\le 1\,500$ | $z=0$ | 4, 11 | |
| 14 | 2 | $n\le 1\,500$ | $a,b\le 1\,500$ | $z=0$ | 4–6, 11–13 | |
| 15 | 6 | $n\le 5\,000$ | $a,b\le 5\,000$ | $z=0$ | 4–7, 11–14 | |
| 16 | 2 | $a,b\le 200\,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