#!/usr/bin/perl -w

use strict;

my (
   $input,
   @distribution,
   $max_key_size,
   $min_confidence,
   %found_keys,
   $key_size,
   @strides,
   $i,
   $j,
   $key,
);

$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;
   foreach $j (unpack 'C*', $input)
   {
      $strides[$i++] .= chr($j);
      $i %= $key_size;
   }

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

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

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

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

      my $average_error = 0;
      foreach $j (@offsets)
      {
         $average_error += $$j[0];
      }
      $average_error /= 26;
      my $error_deviation = 0;
      foreach $j (@offsets)
      {
         my $delta = $$j[0] - $average_error;
         $error_deviation += $delta * $delta;
      }
      $error_deviation = sqrt($error_deviation / 26);

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

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

         $confidence = $margin / $error_deviation;
         $confidence = $confidence < .25 ? 0 :
                       $confidence < .5 ? 1 :
                       $confidence < 1 ? 2 : 3;
      }

      $key .= chr($offset);
      if( !defined($local_confidence) || $local_confidence > $confidence )
      {
         $local_confidence = $confidence;
         if( $local_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)
   {
      $key .= $j;
      $found_keys{$key} = 0;
   }

   $min_confidence = $local_confidence;
}

foreach $key (sort {$found_keys{$b} <=> $found_keys{$a} ||
                    length($b) <=> length($a)}
              keys %found_keys)
{
   last if !$found_keys{$key};

   print
   (
      (map {chr(ord('A') + $_)} unpack 'C*', $key),
      "\n",
      (map {chr(ord('a') + (26 - $_) % 26)} unpack 'C*', $key),
      "\n"
   );
   last;
}