Zadaca

Ο Μίρκο έλαβε μια εργασία για το σπίτι να υπολογίσει τον μεγαλύτερο κοινό διαιρέτη των δύο θετικών ακεραίων ~A~ και ~B~. Δεδομένου ότι οι αριθμοί είναι αρκετά μεγάλοι, ο δάσκαλος του έδωσε ~N~ μικρότερους ακέραιους με το γινόμενο ~A~ και ~M~ ακέραιους με το γινόμενο ~B~.
Ο Mirko θα ήθελε να επαληθεύσει το αποτέλεσμά του, γι' αυτό σας ζήτησε να γράψετε ένα πρόγραμμα για να λύσετε το πρόβλημά του.
Εάν το αποτέλεσμα είναι μεγαλύτερο από 9 ψηφία, εξάγετε μόνο τα τελευταία 9 ψηφία.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον θετικό ακέραιο αριθμό ~N\;(1 \leq N \leq 1000)~.
Η δεύτερη γραμμή εισόδου περιέχει N θετικούς ακέραιους χωρισμένους σε διάστημα μικρότερους από ~1\,000\,000\,000~, των οποίων το γινόμενο είναι ο αριθμός ~A~.
Η τρίτη γραμμή εισόδου περιέχει τον θετικό ακέραιο ~M\,(1 \leq M \leq 1000)~.
Η τέταρτη γραμμή εισόδου περιέχει ~M~ θετικούς ακέραιους χωρισμένους σε διάστημα μικρότερους από ~1\,000\,000\,000~, των οποίων το γινόμενο είναι ο αριθμός ~B~.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει τον μεγαλύτερο κοινό διαιρέτη των αριθμών ~A~ και ~B~. Εάν το αποτέλεσμα είναι μεγαλύτερο από 9 ψηφία, βγάζετε μόνο τα τελευταία (λιγότερο σημαντικά) 9 ψηφία.

Παραδείγματα

input

3
2 3 5
2
4 5

output

10

Επεξήγηση του 1ου παραδείγματος:

Ο μεγαλύτερος κοινός διαιρέτης των αριθμών ~A = 30~ και ~B = 20~ ισούται με 10.

input

4
6 2 3 4
1
1

output

1

input

3
358572 83391967 82
3
50229961 1091444 8863

output

000012028