--->
1 задач
<---
Вам дан массив целых чисел длины N . Пусть s 1 , s 2 , ... , s q - массив его непустых подпоследовательностей, отсортированный в лексикографическом порядке.
Подпоследовательностью массива называется массив, полученным путем вычеркивания нескольких (возможно, 0) элементов из изначального массива. Заметьте, что некоторые подпоследовательности могут быть одинаковыми, поэтому q = 2 N - 1 .
Массив A лексикографически меньше массива B , если A i < B i , где i - первая позиция, в которой массивы различаются, или если A - строгий префикс B .
Определим хеш массива s , состоящего из элементов v 1 , v 2 , ... , v p , как: h ( s ) = ( v 1 · B p - 1 + v 2 · B p - 2 + ... + v p - 1 · B + v p ) mod M , где B и M - данные числа.
Посчитайте h ( s 1 ) , h ( s 2 ) , ... , h ( s K ) для данного K .
В первой строке содержатся числа N , K , B , M ( 1 ≤ N ≤ 100000 , 1 ≤ K ≤ 100000 , 1 ≤ B , M ≤ 1000000 ).
Во второй строке содержится N чисел a 1 , a 2 , a 3 , ... , a N ( 1 ≤ a i ≤ 100000 ).
Гарантируется, что во всех тестах K ≤ 2 N - 1 .
Выведите K строк, j -я строка должна содержать h ( s j ) и длину s j .
Решения, работающие при 1 ≤ a 1 , a 2 , ..., a N ≤ 30 , будут оцениваться в 60 баллов.
2 3 1 5 1 2
1 1 3 2 2 1
3 4 2 3 1 3 1
1 1 1 1 0 2 2 2
5 6 23 1000 1 2 4 2 3
1 1 25 2 25 2 577 3 274 4 578 3