{$M 65520,0,655360}
program erdvelaivis;
  { 139 u‘davinys }
  const MAX_N = 100; { maksimalus bazi— skai‡ius }
        MAX_K = 100; { maksimalus kreditas }
        DAUG = 1000; { atstumas tarp dviej— bazi— nebus didesnis u‘ žŤ }
  type  bazes = array [1..MAX_N] of record  { duomenys apie bazes }
                                      k, x, y, z: integer;
                                    end;

        atstumai = array [1..MAX_N, 1..MAX_N] of real;
                      { atstumai tarp bazi— }
        marsrutas = array [1..MAX_N, 0..MAX_K] of integer;
        { [a, kr] parodo, Ť kuri… bazŠ reikia skristi iž baz‚s a, }
        { turint kredit… kr }
        t_atst = array[1..MAX_N, 0..MAX_K] of real;
        atstumas_n = ^t_atst;
        { parodo, koks trumpiausias atstumas iki n-tosios baz‚s }
        { jei esame baz‚je a ir turime kr kredit— }

  procedure skrieti (v, san, { rezervuaro talpa ir kuro s…naudos ilgio vnt. }
                     kr, n: integer; { turimas kreditas ir bazi— skai‡ius }
                     baz: bazes; var kur: marsrutas);
  { randa optimal— skridimo maržrut… }
    var ats: atstumai;
        min,
        max_kel: real;   { ilgiausias kelias, kurŤ galima }
                         { nuskristi su pilnu baku kuro }
        ats_n: atstumas_n; { trumpiausi atstumai iki n-tosios baz‚s }
        i, k, a, b, lik: integer;

    procedure atstum (n: integer; baz: bazes;
                      var ats: atstumai);
    { suskai‡iuoja atstumus tarp bazi— }
      var i, j: integer;
          d: real;
    begin
      for i := 1 to n do
        for j := 1 to n do
          ats[i, j] := 0;
      for i := 1 to n do
        for j := i+1 to n do
          begin
            d := sqrt(sqr(baz[i].x - baz[j].x) +
                      sqr(baz[i].y - baz[j].y) +
                      sqr(baz[i].z - baz[j].z));
            ats[i, j] := d;
            ats[j, i] := d;
        end;
    end; { atstum }

    procedure inicializuoti (var kur: marsrutas; var ats_n: atstumas_n);
    { suteikia pradines reikžmes reikiamiems kur ir ats_n elementams }
    { vartoja globalius kintamuosius n, kr, max_kel, ats, baz }
    { ži— kintam—j— reikžmi— nekei‡ia }
      var i, k: integer;
    begin
      new (ats_n);
      { u‘pildysime kur[i, 0] }
      for i := 1 to n-1 do
        if (baz[i].k = 0) and (max_kel >= ats[i, n])
           then begin
                  kur[i, 0] := n;
                  ats_n^[i, 0] := ats[i, n];
                end
           else kur[i, 0] := -1; { nuskristi negalima }
      { u‘pildysime kur[n, k] }
       for k := 0 to kr do
         begin
           kur[n, k] := 0; { niekur skristi nebereikia }
           ats_n^[n, k] := 0;
         end;
    end; { inicializuoti }

    procedure skristi_a (a, k: integer; { skrenda iž a su kreditu k }
                         var kur: marsrutas; var ats_n: atstumas_n);
    { randa trumpiausi… keli… iž baz‚s a Ť bazŠ n, kai turima k kredit— }
    { vartojami globalieji kintamieji max_kel, baz, ats }
    { ži— kintam—j— reikžm‚s nekei‡iamos }
      var min: real; { mininalus atstumas nuo baz‚s a iki baz‚s n }
          b, lik: integer; { kredito likutis }
    begin
      min := DAUG; { trumpiausias atstumas nuo baz‚s a iki n }
      kur[a, k] := -1; { kelio kol kas neradome }
      for b := 1 to n do { skrendame Ť bazŠ b }
        if (ats[a, b] <= max_kel) and (a <> b) { baz‚ b pasiekiama }
        then begin
               if (baz[a].k = 0) and (baz[b].k = 0)
                  then lik := k - 1
                  else lik := k - baz[a].k;
               if (kur[b, lik] >= 0) { jei iž baz‚s b pasieksim n-t…j… bazŠ }
                  and (min > (ats[a, b] + ats_n^[b, lik]))
                  { ir naujas kelias yra trumpesnis }
                  then begin
                         min := ats[a, b] + ats_n^[b, lik];
                         kur[a, k] := b;
                         ats_n^[a, k] := min;
                       end;
                end;
    end; { skristi }

  begin
    { rasime atsumus tarp bazi— }
    atstum (n, baz, ats);
    max_kel := v/san;
    inicializuoti (kur, ats_n);
    { u‘pildysime likusi… lentel‚s dalŤ }
    for k := 1 to kr do
      begin { turime k kredit— }
        { pirmiausia skrendame iž bazi—, kuriose reikia mok‚ti }
        for a := 1 to n-1 do { skrendame iž baz‚s a }
          if k < baz[a].k { jei iž žios baz‚s negalima ižskristi }
          then kur[a, k] := -1
          else if baz[a].k <> 0
                  then skristi_a (a, k, kur, ats_n);
        { tuomet skrendame iž bazi—, kuriose nereikia mok‚ti }
        for a := 1 to n-1 do
          if baz[a].k = 0
             then skristi_a (a, k, kur, ats_n);
      end;
  end; { skrieti }

  var f: text;
      baz: bazes;
      kur: marsrutas;
      v, san, kr, n, i, j: integer;
begin
  assign (f, 'ERDV.DAT');
  reset (f);
  readln (f, v, san, kr, n);
  for i := 1 to n do
    with baz[i] do
      readln (f, k, x, y, z);
  close(f);
  skrieti (v, san, kr, n, baz, kur);
  assign (f, 'ERDV.REZ');
  rewrite (f);
  i := 1; { skrisime iž pirmosios baz‚s, tur‚dami kr kredit— }
  repeat
    writeln (f, i);
    j := i;  { Ťsimename bazŠ iž kurios ižskridome }
    i := kur[i, kr]; { atskridome Ť ži… bazŠ }
    kr := kr - baz[j].k; { perskai‡iuojame kreditus }
  until i = n;
  writeln (f, n);
  close (f);
end.