Диас и Арыстан интересуются спортивным программированием и хотят попасть в ACM Club нашего чудесного SDU. Для этого они сходили на выставку клубов и выяснили, что туда попадают только те, кто готовят первоклассный маклюбе и способны решить одну непростую задачу. Диас и Арыстан не могли похвастаться кулинарными навыками и решили сначала научиться готовить, а вас попросили помочь с решением задачи, условие которой описано ниже.

Вам дан массив $$$a$$$ длины $$$n$$$ состоящий из положительных целых чисел. Обозначим $$$f(a)$$$ как массив $$$b$$$ длины $$$n-1$$$, где $$$b_i = gcd(a_1 + \dots + a_i, a_{i+1} + \dots + a_n)$$$. Будем применять операцию $$$a = f(a)$$$ до тех пор, пока размер массива $$$a$$$ не станет равным $$$1$$$. Выведите единственное оставшееся число в массиве.

Здесь $$$gcd(x, y)$$$ означает наибольший общий делитель (НОД) чисел $$$x$$$ и $$$y$$$.