== include(page="template/taskheader" task_id="ppal") ==

Poveste şi cerinţă...

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 lexicografic decât orice literă.
 
h2. Cerinţă
 
Fiind date un şir de litere mici şi două numere naturale $p$, respectiv $q$, se cere să se determine descompunerea cu numărul de ordine $q$ din mulţimea tuturor soluţiilor ordonate lexicografic formate din $p$ palindroame.

h2. Date de intrare

Fişierul de intrare $ppal.in$ ...

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.

h2. Date de ieşire

În fişierul de ieşire $ppal.out$ ...

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ă.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $0 < p ≤ n ≤ 500$
* $0 < q ≤ 10^16^ - 1$
* Numărul maxim de perechi $p q$ nu va depăşi $50 000$

h2. Exemplu
table(example). |_. ppal.in |_. ppal.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 9
abbbabaca
5 3
5 1
5 5
3 1
3 2
| a bbb aba c a
a b b bab aca
0
abbba b aca
0

|
h3. Explicaţie

...

Primele două rezulte corespund celei de a treia descompunere din exemplul anterior, respectiv a primei descompuneri din exemplul anterior. Pentru perechea $5 5$ nu există $5$ soluţii, deci se scrie $0$. Pentru perechea $3 1$ există o singură descompunere de $3$ palindroame. Pentru $3 2$ a doua soluţie nu există, deci se scrie $0$.

== include(page="template/taskfooter" task_id="ppal") ==