Задається час у секундах. Виведіть заданий час у форматі: ~hh:mm:ss~

Input

У вхідному потоці міститься ціле число не більше 86400.

Output

У вихідний потік вивести час у форматі ~hh:mm:ss~ або повідомлення ~error~, якщо час задається від'ємним числом

Sample Input 1

2021

Sample Output 1

00:33:41

Sample Input 2

-100

Sample Output 2

error

Назвемо відстаню між двома значеннями масиву різницю індексів ~j-i, (i \le j)~.

Задається масив цілих чисел ~a~. Знайдіть мінімальну відстань між будь-якою парою однакових елементів у цьому масиві. Якщо таких елементів не існує, то вивести -1.

Input

Перший рядок вхідного потоку містить ціле число ~n~ (~1 \le n \le 10^3~) - кількість елементів масиву ~a~.

Другий рядок містить елементи масиву ~a~ (~1 \le a_i \le 10^5~), які розділяються пропуском.

Output

У вихідний потік вивести шукану мінімальну відстань або -1.

Sample Input 1

6
7 1 3 4 1 7

Sample Output 1

3

Sample Input 2

5
1 2 3 4 10

Sample Output 2

-1

Задається рядок ~s~, який містить лише малі англійські літери. Даний рядок повторюється велику кількість разів і в результаті утворюється достатньо довгий рядок.

Завдання: знайти кількість входжень літери ~a~ в утворений довгий рядок до ~n~-го символа включно.

Наприклад, задається рядок ~s = abcac~ та ~n=10~. Перші десять символів утвореного рядка ~abcacabcac~ і кількість повторень літери ~a~ рівна 4.

Input

Перший рядок вхідного потоку містить рядок ~s~ (~1 \le |s| \le 100~).

Другий рядок містить ціле число ~n~ (~1 \le n \le 10^{12}~).

Output

Вивести шукану кількість входжень літери ~a~ до ~n~-го символа включно.

Sample Input 1

abcac
10

Sample Output 1

4

Sample Input 2

aba
10

Sample Output 2

7

Sample Input 3

a
1000000000000

Sample Output 3

1000000000000

Задаються чотири цілих числа ~A~, ~B~, ~C~ і ~D~.

Знайдіть кількість цілих чисел між ~A~ і ~B~(включно), які не діляться ні на ~C~, ні на ~D~.

Input

Вхідний потік містить чотири цілі числа ~A, B, C, D~ (~1 \le A \le B \le 10^{18}~), які розділяються пропуском.

Output

У вихідний потік вивести шукану кількість чисел.

Sample Input 1

4 9 2 3

Sample Output 1

2

Sample Input 2

10 40 6 8

Sample Output 2

23

Ви граєте в матричну гру з такими налаштуваннями та правилами:

• Вам дається матриця ~A~ розмірності ~n \times m~. Кожна клітинка матриці містить цілі числа. Коли гравець проходить через клітинку, його рахунок збільшується на число, записане в цій клітинці, і число в клітинці стає рівним 0. Якщо число у клітинці від'ємне, то кількість балів зменшиться на це число.

• Гравець починає гру з будь-якої клітинки в першому ряду і може рухатися вліво, вправо або вниз.

• Гра закінчується, коли гравець досягає останнього ряду і зупиняється.

Який максимальний бал зможе отримати гравець.

Input

Перший рядок вхідного потоку містить цілі числа ~n,m~ (~1 \le n \times m \le 4 \times 10^6~)

Наступні ~n~ рядків містять по ~m~ цілих чисел - елементи ~A_{ij}~ (~-250 \le A_{ij} \le 250~) матриці ~A~. Числа у рядках розділяються пропуском.

Output

У вихідний потік вивести максимальний бал гравця.

Sample Input 1

4 5
1 2 3 -1 -2
-5 -8 -1 2 -150
1 2 3 -250 100
1 1 1 1 20

Sample Output 1

37