program kaladeliu_perdeliojimas;
  { 10 u‘davinys }
{----------------------------------------------------------}
  const K = 1000;      { kalad‚li— skai‡ius }
  type kalad = array [1..K] of char;
       numeracija = array [1..K] of 0..K;

  procedure perstatyti (a : kalad;     { pradin‚ eil‚ }
                        var b : kalad; { perd‚liota eil‚ }
                        var galima : boolean);
  { nustatoma, ar galima kalad‚les perd‚lioti taip, kad nei viena raid‚
    nepasilikt— savo vietoje ir jei galima - kalad‚l‚s perstatomos }
    var raid : array ['A'..'Z'] of 0..K; { raid‘i— kartojim— skai‡ius }
        numer,            { raid‘i— numeracija }
        kur : numeracija; { kur yra tam tikru numeriu pa‘ym‚ta kalad‚l‚ }
        nau_num,          { perstatytos kalad‚l‚s numeris }
        i, nm : integer;
        j : char;
  begin
    for j := 'A' to 'Z' do
      raid[j] := 0;
    for i := 1 to K do  { kiek kart— pasikartoja kiekviena raid‚ }
      raid[ a[i] ] := raid[ a[i] ] + 1;
    galima := true;
    for j := 'A' to 'Z' do
      galima := galima and (raid [j] <= K div 2);
    { jei kalad‚li— perstatyti negalima, darbas baigiamas }
    if not galima then exit;
    { jei galima - perstatin‚jama }
    { sunumeruojamos kalad‚les ir sudaroma lentel‚, padedanti rasti
      sunumeruotas kalad‚les }
    nm := 0;
    for j := 'A' to 'Z' do
      for i := 1 to K do
        if a[i] = j
           then begin
                  nm := nm + 1;
                  numer[i] := nm;
                  kur[nm] := i
                end;
    { perskai‡iuojami kalad‚li— numeriai ir perstatomos kalad‚l‚s }
    for i := 1 to K do
      begin
        nau_num := (numer[i] + K div 2 - 1) mod K + 1;
        { i-tosios kalad‚l‚s naujas numeris }
        b[kur[nau_num]] := a[i]
      end
  end;
{----------------------------------------------------------}
var i : integer;
    v : string;
    f : text;
    galima : boolean;  { ar galima kalad‚les perd‚lioti }
    a, b : kalad;      { pradinis ir perd‚liotas kalad‚li— masyvai }
begin
  write ('­veskite pradini— duomen— bylos vard…: ');
  readln (v);
  assign (f, v);       { Ťvedami pradiniai duomenys }
  reset (f);
  for i := 1 to K do
    read (f, a[i]);
  close (f);

  perstatyti (a, b, galima);

  write ('­veskite rezultat— bylos vard…: ');
  readln (v);
  assign (f, v);
  rewrite (f);
  if galima     { jei perstatyti galima }
     then for i := 1 to K do
             write (f, b[i])
     else writeln (f, 'NEGALIMA');
  close (f)
end.