Преподаватель Д. очень любит давать контрольные работы; вот и сегодняшний день не стал исключением. Однако на контрольной Д. дал очень странную задачу, которую Вам и требуется решить...

Напомним несколько классических определений. Пусть дан массив A из n целых чисел [a₁, a₂, ..., a_n]. Последовательность [b₁, b₂, ..., b_m] будет называть подмассивом данного массива, если существует такое l, 1 ≤ l ≤ n - m + 1, что a_l = b₁, a_l + 1 = b₂, ..., a_{l + m - 1} = b_m.

Разные массивы даже одинаковой длины могут иметь разное количество непустых подмассивов. Например, массив [1, 1, 1] имеет три различных подмассива ([1], [1, 1], [1, 1, 1]), в то время как массив [1, 2, 3] - шесть ([1], [1, 2], [1, 2, 3], [2], [2, 3], [3]).

Массивы можно сравнивать лексикографически. Массив C = [c₁, c₂, ..., c_k] лексикографически меньше массива D = [d₁, d₂, ..., d_l], если выполнено одно из двух условий:

1. Массив C короче массива D и является его префиксом, то есть k < l, и при этом c₁ = d₁, c₂ = d₂, ..., c_k = d_k;
2. В первой позиции, в которой они отличаются, у массива C стоит меньший элемент, то есть существует такое целое положительное p ≤ min(k, l), что c₁ = d₁, c₂ = d₂, ..., c_p - 1 = d_p - 1 и c_p < d_p.

А вот и условие задачи. Пусть дан массив A = [a₁, a₂, ..., a_n] и целое положительное число k. Упорядочим все подмассивы А в лексикографическом порядке. Какой подмассив идёт в полученном упорядоченном списке k-м?