A-Z Cat

Time Limit : 5 sec, Memory Limit : 131072 KB

A: A-Z Cat / A-Z キャット

物語

あいずにゃんは若ヶ松高校のプログラミングコンテスト部,通称ぷろこん部に所属する2年生である.とてつもなくかわいい.あいずにゃんは友達のジョイに頼まれて猫を預かることになった.A-Z キャットと呼ばれる珍種の猫である.あいずにゃんは預かった A-Z キャットを「あいずにゃん 2 号」と (勝手に) 名付け,大層可愛がった.

A-Z キャットは特定の条件を満たす文字列を好むとされる.そこであいずにゃんが試しに文字列を与えてみると,あいずにゃん 2 号は文字列の一部を爪で切り取った後,満足げな表情を浮かべた.どうやら,好みの文字列に書き換えようとしているようだ.

天使のごとくかわいいあいずにゃんにぞっこんである D のひとは,あいずにゃんのために A-Z キャットが好む文字列の条件を見つけ出した.それは 'A' と 'Z' が交互に繰り返される文字列であり,かつ 'A' から始まり 'Z' で終わる文字列である.A-Z キャットはとても賢いので,最小限の文字消去で好みの文字列に変換しようとする.あいずにゃんにいい格好をしたい D のひとは,与えられた 'A' と 'Z' のみからなる文字列を A-Z キャットがどのような文字列に変換するか求めるプログラムを書くことにした.

問題

英大文字のみからなる文字列 S が与えられる.S の任意の文字を好きなだけ削除することで,'A' と 'Z' が交互に出現し,かつ 'A' から始まり 'Z' で終わる文字列を作る.削除回数を最小化したとき得られる文字列を求めよ.

入力形式

入力として文字列 S が1行に与えられる.S は英大文字のみからなり,1 ≤ |S| ≤ 20を満たす.

出力形式

S に対し最小回数の文字削除を行って得られる,'A' と'Z' が交互に出現し,かつ 'A' から始まり 'Z' で終わる文字列を 1 行に出力せよ.どのような文字削除を行っても条件を満たす文字列が得られない場合は -1 を 1 行に出力せよ.

入力例1

AIZUNYANPEROPERO

出力例1

AZ

入力例2

AZAZ

出力例2

AZAZ

入力例3

ZDDYAZAWABDDZAZPIDDA

出力例3

AZAZAZ

入力例4

ZZZZAAAAAA

出力例4

-1

Source: Ritsumeikan University Programming Camp 2015 , Problem set from Hokkaido University teams, Shiga, Japan, 2015-03-16