Условие:
Вам дана бинарная∗
строка s
длины n
.
Ваша задача — найти любую подпоследовательность†
p
строки s
такую, что:
Подпоследовательность p
является неубывающей.
Пусть x
обозначает строку, полученную путем удаления всех символов p
из s
, сохраняя порядок оставшихся символов. Строка x
должна быть палиндромом‡
.
Вам нужно вывести любую допустимую подпоследовательность p
, которая удовлетворяет обоим условиям. Если такой подпоследовательности не существует, выведите −1
.
Обратите внимание, что пустая строка является как неубывающей, так и палиндромом.
∗
Бинарная строка — это строка, состоящая из символов '0' и '1'.
†
Подпоследовательность строки s=s1s2…sn
— это последовательность p=si1si2…sik
такая, что 1≤i1<i2<…<ik≤n
. Символы выбираются в порядке, но не обязательно смежно. Обратите внимание, что пустая строка является подпоследовательностью любой строки.
‡
Строка t=t1t2…tm
является палиндромом, если ti=tm−i+1
для всех 1≤i≤m
. Другими словами, строка читается одинаково вперед и назад.
Первая строка содержит одно целое число t
(1≤t≤3000
) — количество наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число n
(1≤n≤10
) — длина строки.
Вторая строка содержит бинарную строку s
длиной n
.
