נתונות שתי סדרות של מספרים שלמים באורך $n$, המסומנות $B=[b_1,\ldots,b_n]$ ו־$C=[c_1,\ldots,c_n]$. עבור סדרה של מספרים שלמים אי־שליליים $D=[d_1,\ldots,d_n]$ באורך $n$, נסמן ב־$S(D)$ את קבוצת כל האינדקסים $i$ שעבורם $d_i=0$, ונגדיר $f(D)=\sum_{i\in S(D)}b_i$ ו־$g(D)=\prod_{i\in S(D)}c_i$. בפרט, אם $S(D)$ ריקה, אז $f(D)=0$ ו־$g(D)=1$.

ל־小 L יש סדרה של מספרים שלמים חיוביים $A=[a_1,\ldots,a_n]$ באורך $n$. הוא יכול לשנות את הסדרה $A$ כך:

• בוחרים שני אינדקסים סמוכים $i,j$ בסדרה $A$ (כלומר $1\le i,j\le n$ וגם $|i-j|=1$). אם $a_i\le a_j$, משנים את $a_j$ ל־$a_j-a_i$, ובו בזמן משנים את $a_i$ ל־$0$.

小 L יכול לבצע מספר כלשהו של פעולות שינוי, ויכול גם לא לבצע שום שינוי. מבין כל הסדרות $D$ שאפשר לקבל מהסדרה $A$ באמצעות הפעולות האלה, הוא רוצה למצוא את הערך המרבי של $f(D)$ ואת סכום ערכי $g(D)$. עזרו לו למצוא את שני הערכים. באופן פורמלי, נסמן ב־$T(A)$ את קבוצת כל הסדרות שאפשר לקבל מ־$A$ באמצעות הפעולות האלה. עליכם למצוא את $\max_{D\in T(A)}f(D)$ ואת $\sum_{D\in T(A)}g(D)$. מכיוון שהסכום $\sum_{D\in T(A)}g(D)$ עשוי להיות גדול, יש לחשב רק את השארית שלו מודולו $1\,000\,000\,007$.

קלט

קראו את הנתונים מהקובץ sequence.in.

הבעיה מכילה כמה מקרי בדיקה.

השורה הראשונה מכילה שני מספרים שלמים אי־שליליים $c,t$, המציינים בהתאמה את מספר הבדיקה ואת מספר מקרי הבדיקה. $c=0$ מציין שזו דוגמה.

לאחר מכן ניתנים מקרי הבדיקה לפי הסדר. עבור כל מקרה בדיקה:

השורה הראשונה מכילה מספר שלם חיובי $n$, אורך הסדרה.

השורה השנייה מכילה $n$ מספרים שלמים חיוביים $a_1,\ldots,a_n$, המתארים את הסדרה $A$.

השורה השלישית מכילה $n$ מספרים שלמים $b_1,\ldots,b_n$, המתארים את הסדרה $B$.

השורה הרביעית מכילה $n$ מספרים שלמים חיוביים $c_1,\ldots,c_n$, המתארים את הסדרה $C$.

פלט

כתבו את הפלט לקובץ sequence.out.

עבור כל מקרה בדיקה הדפיסו שורה אחת בלבד ובה שני מספרים שלמים: $\max_{D\in T(A)}f(D)$ והשארית של $\sum_{D\in T(A)}g(D)$ מודולו $1\,000\,000\,007$, בהתאמה. שימו לב: אין לחשב את $\max_{D\in T(A)}f(D)$ מודולו $1\,000\,000\,007$.

הבעיה כוללת שתי שאלות, ותשובה נכונה לכל אחת מהן יכולה לזכות בניקוד חלקי. לפרטי הניקוד ראו ״ניקוד״.

דוגמאות

קלט 1

0 3
3
5 6 6
3 6 9
1 2 3
6
1 1 4 5 1 4
-1 1 -1 1 -2 2
1 1 1 1 1 1
8
4 2 4 2 2 2 4 4
-2 4 9 -3 4 8 7 8
1 1 1 1 1 1 1 1

פלט 1

15 10
1 18
37 48

הסבר

הדוגמה כוללת שלושה מקרי בדיקה.

במקרה הראשון אפשר לקבל את ארבע הסדרות האלה:

• $D=[5,6,6]$, $f(D)=0$, $g(D)=1$;
• $D=[0,1,6]$, $f(D)=3$, $g(D)=1$;
• $D=[5,0,0]$, $f(D)=6+9=15$, $g(D)=2\times3=6$;
• $D=[0,0,5]$, $f(D)=3+6=9$, $g(D)=1\times2=2$.

לכן $\max_{D\in T(A)}f(D)=\max\{0,3,15,9\}=15$ ו־$\sum_{D\in T(A)}g(D)=1+1+6+2=10$.

דוגמה 2

ראו את sequence/sequence2.in ואת sequence/sequence2.ans בתיקיית המתחרים.

הדוגמה מקיימת את מגבלות בדיקות $3,4$.

דוגמה 3

ראו את sequence/sequence3.in ואת sequence/sequence3.ans בתיקיית המתחרים.

הדוגמה מקיימת את מגבלות בדיקות $5,6$.

דוגמה 4

ראו את sequence/sequence4.in ואת sequence/sequence4.ans בתיקיית המתחרים.

הדוגמה מקיימת את מגבלות בדיקה $7$.

דוגמה 5

ראו את sequence/sequence5.in ואת sequence/sequence5.ans בתיקיית המתחרים.

הדוגמה מקיימת את מגבלות בדיקות $11,12$.

דוגמה 6

ראו את sequence/sequence6.in ואת sequence/sequence6.ans בתיקיית המתחרים.

הדוגמה מקיימת את מגבלות בדיקות $16\sim18$.

מגבלות

נסמן ב־$N$ את סכום ערכי $n$ של כל מקרי הבדיקה בבדיקה אחת. בכל מקרי הבדיקה מובטח:

• $1\le t\le20$;
• $1\le n\le5\,000$, $N\le4\times10^4$;
• לכל $1\le i\le n$ מתקיים $1\le A_i\le10^9$;
• לכל $1\le i\le n$ מתקיים $-10^9\le B_i\le10^9$;
• לכל $1\le i\le n$ מתקיים $1\le C_i\le10^9$.

תכונה מיוחדת A: מובטח כי $A_1=A_2=\cdots=A_n=1$.

תכונה מיוחדת B: מובטח שלכל $1\le i\le n$, הערך $A_i$ נוצר באקראי באופן אחיד ובלתי תלוי מתוך $[1,10^9]$.

ניקוד

עבור כל בדיקה:

• תשובות נכונות לערך $\max_{D\in T(A)}f(D)$ בכל מקרי הבדיקה מזכות ב־$40\%$ מניקוד הבדיקה;
• תשובות נכונות לשארית של $\sum_{D\in T(A)}g(D)$ מודולו $1\,000\,000\,007$ בכל מקרי הבדיקה מזכות ב־$60\%$ מניקוד הבדיקה.

שימו לב: גם אם עונים רק על אחת משתי השאלות, יש להדפיס שני מספרים שלמים לפי פורמט הפלט, בהתאמה לתשובות לשתי השאלות.