Problem 2299: ppal

Un cuvânt format din literele mici ale alfabetului englezesc este palindrom dacă citind de la stânga la dreapta sau de la dreapta la stânga avem acelaşi cuvânt. De exemplu ghihg sau lool sunt palindroame.
Să considerăm un şir format numai din litere mici ale alfabetului englez. În acest şir se pot introduce pe alocuri câte un spaţiu astfel încât să se transforme într-un text ce conţine doar cuvinte palindroame. De exemplu, abbbabaca se poate despărţi în cuvinte palindrom în mai multe moduri, dintre care exemplificăm toate descompunerile în $5$ palindroame în ordine lexicografică:

a b b bab aca
a bbb a b aca
a bbb aba c a
abbba b a c a

Să considerăm toate descompunerile unui şir în exact $p$ palindroame, soluţiile obţinute fiind aranjate în ordine lexicografică. Caracterul (spaţiu) este mai mic decât orice literă.

Cerinţă

Fiind date un şir de litere mici şi două numere naturale $p$ respectiv $q$ , să se determine descompunerea cu numărul de ordine $q$ din mulţimea tuturor soluţiilor ordonate lexicografic formate din p palindroame.

Date de intrare

Fişierul de intrare ppal.in conţine pe prima linie numărul natural $n$ . Pe cea de a doua linie se află un şir de $n$ litere mici ale alfabetului englez. Începând cu linia a $3$ -a până la sfârşitul fişierului fiecare linie conţine câte o pereche de numere naturale $p$ şi $q$ separate prin câte un spaţiu.

Date de ieșire

Fişierul de ieşire ppal.out va conţine pentru fiecare pereche de numere $p \ q$ a fişierului de intrare câte o linie pe care se va scrie descompunerea cu numărul de ordine $q$ din mulţimea tuturor soluţiilor formate din $p$ palindroame, aranjate lexicografic, sau $0$ (zero) în cazul în care soluţia cu numărul de ordine $q$ nu există.

Restricții și precizări

$0 < p \leq n \leq 500$
$0 < q \leq 999 \ 999 \ 999 \ 999 \ 999 \ 999$
Numărul maxim de perechi $p \ q$ nu va depăşi $250 \ 000$

Exemplu

ppal.in

9
abbbabaca
5 3
5 1
5 5
3 1
3 2

ppal.out

a bbb aba c a
a b b bab aca
0
abbba b aca
0

Explicație

A treia descompunere din exemplul anterior
Prima descompunere din exemplul anterior
Nu există $5$ soluţii, deci se scrie $0$
Există o singură descompunere de $3$ palindroame
A doua souţie nu există, deci se scrie $0$

ppal