#!/usr/bin/perl -w

use strict;

my (
   $input,
   @distribution,
   $max_key_size,
   $min_confidence,
   %found_keys,
   $key_size,
   @strides,
   $i,
   $j,
   $key,
   @dist,
   @offsets,
   $local_confidence,
   $error,
   $diff,
);

$input = join '', <>;

$input = lc $input;
$input =~ y/a-z//cd;
$input =~ y/a-z/\0-\31/;

@distribution = (
   .07969,
   .01419,
   .02439,
   .04446,
   .12517,
   .01936,
   .02392,
   .06414,
   .07019,
   .00191,
   .01048,
   .04236,
   .02005,
   .06546,
   .07705,
   .01600,
   .00178,
   .05374,
   .05909,
   .09919,
   .03234,
   .00782,
   .02400,
   .00143,
   .02101,
   .00065,
);

$max_key_size = length($input) / 5;
if( $max_key_size > 64 )
{
   $max_key_size = 64;
}

$min_confidence = 0;

%found_keys = ("" => 1);
for($key_size = 1; $key_size < $max_key_size; $key_size++)
{
   @strides = ();
   $#strides = $key_size - 1;

   $i = 0;
   map
   {
      $strides[$i++] .= chr($_);
      $i %= $key_size;
   } unpack 'C*', $input;

   $key = "";
   $local_confidence = 26 * 26;
   for($i = 0; $i < $key_size; $i++)
   {
      @dist = map {0} 0..25;
      map {$dist[$_]++} unpack 'C*', $strides[$i];
      @dist = map {$_ / length($strides[$i])} @dist;

      @offsets = ();
      foreach $j (0..25)
      {
         $error = 0;
         map
         {
            $diff = $distribution[$_] - $dist[($_ + $j) % 26];
            $error += $diff * $diff;
         } 0..25;

         push @offsets, [$error, $j];
      }

      @offsets = sort {$$a[0] <=> $$b[0]} @offsets;

      my $average_error = 0;
      map {$average_error += $$_[0]} @offsets;
      $average_error /= 26;

      my $error_deviation = 0;
      map
      {
         $diff = $$_[0] - $average_error;
         $error_deviation += $diff * $diff;
      } @offsets;

      $error_deviation = sqrt($error_deviation / 26);

      my ($offset, $confidence);
      $offset = $confidence = 0;

      if( $error_deviation > 1e-6 )
      {
         $offset = $offsets[0][1];

         $confidence = ($offsets[1][0] - $offsets[0][0]) / $error_deviation;
         $confidence = $confidence < .25 ? 0 :
                       $confidence < .5 ? 1 :
                       $confidence < 1 ? 2 : 3;
      }

      $key .= chr($offset);
      if( $local_confidence > $confidence &&
          ($local_confidence = $confidence) < $min_confidence )
      {
         $key = "";
         last;
      }
   }
   next if exists $found_keys{$key};

   $found_keys{$key} = $local_confidence;

   $j = $key;
   for($i = $key_size; $i < $max_key_size; $i += $key_size)
   {
      $found_keys{$key .= $j} = 0;
   }

   $min_confidence = $local_confidence;
}

foreach $key (sort {$found_keys{$b} <=> $found_keys{$a} ||
                    length($b) <=> length($a)}
              keys %found_keys)
{
   if( $found_keys{$key} )
   {
      print
      (
         (map {chr(ord('A') + $_)} unpack 'C*', $key),
         "\n",
         (map {chr(ord('a') + (26 - $_) % 26)} unpack 'C*', $key),
         "\n"
      );
   }
   last;
}