#include <bits/stdc++.h>

#define FOR(i, n)     for(lli i = 0; i < (lli)(n); ++i)
#define FORU(i, j, k) for(lli i = (j); i <= (lli)(k); ++i)
#define FORD(i, j, k) for(lli i = (j); i >= (lli)(k); --i)

#define X(A) get<0>(A)
#define Y(A) get<1>(A)
#define Z(A) get<2>(A)
#define W(A) get<3>(A)

#define mp make_pair
#define mt make_tuple
#define pb push_back

#ifdef DEBUG
#define DB(x) x
#else
#define DB(x)
#endif

//------------------------------------------------------------------------------

using namespace std;
using lli = long long int;
using llu = long long unsigned;

using pii   = tuple<lli, lli>;
using ppii  = tuple<pii, pii>;
using piii  = tuple<lli, lli, lli>;
using vi    = vector<lli>;
using vii   = vector<pii>;
using viii  = vector<piii>;
using vvi   = vector<vi>;
using vvii  = vector<vii>;
using vviii = vector<viii>;
using pt    = complex<lli>;

//------------------------------------------------------------------------------

template<class A, class B>
ostream& operator<<(ostream& s, pair<A, B> const& a){
  return s << "(" << X(a) << "," << Y(a) << ")";
}

template<class A, class B>
ostream& operator<<(ostream& s, tuple<A, B> const& a){
  return s << "(" << X(a) << "," << Y(a) << ")";
}

template<class A, class B, class C>
ostream& operator<<(ostream& s, tuple<A, B, C> const& a){
  return s << "(" << X(a) << "," << Y(a) << "," << Z(a) << ")";
}

template<class T>
ostream& print_collection(ostream& s, T const& a){
  s << '[';
  for(auto it = begin(a); it != end(a); ++it){
    s << *it;
    if(it != prev(end(a))) s << " ";
  }
  return s << ']';
}

template<class T, size_t I>
ostream& operator<<(ostream& s, array<T, I> const& a) { return print_collection(s, a); }
template<class T>
ostream& operator<<(ostream& s, vector<T> const& a) { return print_collection(s, a); }
template<class T, class U>
ostream& operator<<(ostream& s, multimap<T, U> const& a) { return print_collection(s, a); }
template<class T, class U>
ostream& operator<<(ostream& s, map<T, U> const& a) { return print_collection(s, a); }
template<class T, class U>
ostream& operator<<(ostream& s, unordered_map<T, U> const& a) { return print_collection(s, a); }
template<class T>
ostream& operator<<(ostream& s, set<T> const& a) { return print_collection(s, a); }
template<class T>
ostream& operator<<(ostream& s, unordered_set<T> const& a) { return print_collection(s, a); }

//------------------------------------------------------------------------------

struct uf{
  vi A;
  uf(lli n) : A(n){ FOR(i, n) A[i] = i; }
  lli find(lli a) { return A[a] == a ? a : A[a] = find(A[a]); }
  void unite(lli a, lli b) { A[find(a)] = find(b); }
};

//------------------------------------------------------------------------------

lli gcd(lli a, lli b) { return (a%b==0)?b:gcd(b, a%b); }

struct rational {
  rational(lli a_, lli b_) : a(a_), b(b_) { lli g = gcd(a, b); a /= g; b /= g; if(b < 0) { a *= -1; b *= -1; } }

  bool operator==(rational const& o) const { return a*o.b == o.a*b; }
  bool operator!=(rational const& o) const { return a*o.b != o.a*b; }
  bool operator<(rational const& o) const  { return a*o.b < o.a*b; }
  bool operator<=(rational const& o) const { return a*o.b <= o.a*b; }
  bool operator>(rational const& o) const  { return a*o.b > o.a*b; }
  bool operator>=(rational const& o) const { return a*o.b >= o.a*b; }

  rational operator*(rational const& o) const { return rational(a*o.a, b*o.b); }
  rational operator+(rational const& o) const { return rational(a*o.b + o.a*b, b*o.b); }
  rational operator-(rational const& o) const { return rational(a*o.b - o.a*b, b*o.b); }

  lli a, b;
};

//------------------------------------------------------------------------------

struct node {
  node() : sum(0), dsum(0){ }
  lli sum, dsum;
};

struct tree {
  lli n;
  vector<node> A;
  tree(lli n_) : n((lli)1<<(lli)(log2(n_)+1)), A(2*n) { }

  void push(lli i, lli a, lli b){
    if(i < n){
      lli c = (a+b)/2;
      if(A[i].dsum){
        add__(2*i  , a  , c, A[i].dsum);
        add__(2*i+1, c+1, b, A[i].dsum);
        A[i].dsum = 0;
      }
    }
  }

  void update(lli i){
    A[i].sum = A[2*i].sum + A[2*i+1].sum;
  }

  void add__(lli i, lli a, lli b, lli v){
    A[i].dsum += v;
    A[i].sum += (b-a+1) * v;
  }

  void add_(lli i, lli a, lli b, lli l, lli r, lli v){
    if(l > b) return;
    if(r < a) return;
    if(l <= a && b <= r){
      add__(i, a, b, v);
      return;
    }
    push(i, a, b);
    lli c = (a+b)/2;
    add_(2*i  , a  , c, l, r, v);
    add_(2*i+1, c+1, b, l, r, v);
    update(i);
  }

  void add(lli l, lli r, lli v){
    add_(1, 0, n-1, l, r, v);
  }

  lli query_(lli i, lli a, lli b, lli l, lli r){
    push(i, a, b);
    if(l > b) return 0;
    if(r < a) return 0;
    if(l <= a && b <= r){
      return A[i].sum;
    }
    lli c = (a+b)/2;
    return query_(2*i  , a  , c, l, r)
         + query_(2*i+1, c+1, b, l, r);
  }

  lli query(lli l, lli r){
    return query_(1, 0, n-1, l, r);
  }
};

//------------------------------------------------------------------------------

lli n, m, k;
vi R;
vi T, P, W;
vvi G, RG;

void readInput() {
  cin >> n >> m >> k;
  R.resize(n); FOR(i, n) cin >> R[i];
  T.resize(m); P.resize(m); W.resize(m);
  FOR(i, m) cin >> T[i] >> P[i] >> W[i];
  G.resize(m); RG.resize(m);
  FOR(i, k) {
    lli a, b; cin >> a >> b; a -= 1; b -= 1;
    G[a].pb(b);
    RG[b].pb(a);
  }
}

//------------------------------------------------------------------------------

chrono::time_point<chrono::high_resolution_clock> t_start;

uf UF(0);
vvi comps;

vvi X;
map<lli, map<lli, vii>> A;
lli  score;
lli  avTime;

vi used, valid;

vi depUpdTime;
vi depCost, depWeight;

lli curTime = 0;

using TT = tuple<rational, lli, lli>;
priority_queue<TT> pQueue;

void depUpdate(lli i) {
  if(depUpdTime[i] < curTime) {
    if(used[i]) {
      depCost[i]   = 0;
      depWeight[i] = 0;
    }else{
      depCost[i]   = P[i];
      depWeight[i] = W[i];
      for(auto j : RG[i]) if(!used[j]) {
        depUpdate(j);
        valid[i]     &= valid[j];
        depCost[i]   += depCost[j];
        depWeight[i] += depWeight[j];
      }
      if(valid[i]) pQueue.push(mt(rational(depWeight[i], depCost[i]), curTime, i));
    }
    depUpdTime[i] = curTime;
  }
}

void initSolution() {
  t_start = chrono::high_resolution_clock::now();

  UF = uf(m);
  FOR(i, m) for(auto j : G[i]) UF.unite(i, j);
  comps.resize(m); FOR(i, m) comps[UF.find(i)].pb(i);

  X.resize(m);

  score  = 0;
  avTime = 0; FOR(i, n) avTime += R[i];

  used.assign(m, false);
  valid.assign(m, true);

  depUpdTime.resize(m, -1);
  depCost.resize(m, -1); depWeight.resize(m, -1);

  FOR(i, m) depUpdate(i);
}

void printSolution() {
  // vi E(m, false);
  vvii B(n);
  for(auto p : A) for(auto q : Y(p)) {
      vii &v = B[X(q)];
      v.insert(end(v), begin(Y(q)), end(Y(q)));
    }
  FOR(i, n) {
    cout << B[i].size() << " ";
    reverse(begin(B[i]), end(B[i]));
    for(auto p : B[i]) {
      // for(auto j : RG[X(p)]) if(!E[j]) assert(false);
      // E[X(p)] = 1;
      cout << X(p)+1 << " " << Y(p) << " ";
    }
    cout << "\n";
  }
}

void solve(){
  while(1) {
    auto t_current = chrono::high_resolution_clock::now();
    if(chrono::duration<double>(t_current - t_start).count() >= 2.9) {
      return;
    }
    // ---
    lli i;
    while(1){
      if(pQueue.empty()) return;
      auto p = pQueue.top(); pQueue.pop();
      i = Z(p);
      if(!used[i] && valid[i] && Y(p) == depUpdTime[i] && avTime >= depCost[i]) break;
    }
    // ---
    DB(cerr << "# Best " << i << endl);
    vi NX = X[UF.find(i)];

    set<lli> Ri;
    function<void(lli)> rdeps_i = [&](lli i) {
      if(Ri.count(i) == 0){
        Ri.insert(i);
        for(auto j : RG[i]) rdeps_i(j);
      }
    };
    rdeps_i(i);
    { vi NX_; for(auto j : NX) if(Ri.count(j) == 0) NX_.pb(j); NX = NX_; }
    NX.pb(i);

    auto OLDA = A[UF.find(i)];
    for(auto p : OLDA){
      for(auto q : Y(p)) {
        R[X(p)] += Y(q);
      }
    }
    A[UF.find(i)].clear();
    vi addedBooks;
    map<lli, lli> rdelta;

    map<lli, lli> depAv;
    function<void(lli)> initDepAv = [&](lli i){
      if(depAv.find(i) == depAv.end()) {
        depAv[i] = 0;
        for(auto j : RG[i]) {
          initDepAv(j);
          depAv[j] += 1;
        }
      }
    };
    for(auto j : NX) initDepAv(j);

    lli j = n-1;
    bool ok2 = true;

    multimap<lli, lli> books;
    function<void(lli)> addBook;
    function<void(lli)> addBookDeps;
    addBook = [&](lli i){
      if(T[i] == 1){
        books.insert(mp(P[i], i));
      }else{
        lli cost = P[i];
        while(j >= 0 && cost > 0) {
          lli c = min(R[j], cost);
          if(c > 0) {
            A[UF.find(i)][j].pb(mt(i, c));
            R[j] -= c; rdelta[j] += c;
            cost -= c;
          }
          if(R[j] == 0) j -= 1;
        }
        if(cost == 0){
          addBookDeps(i);
        } else {
          ok2 = false;
        }
      }
    };
    addBookDeps = [&](lli i) {
      DB(cerr << "Add " << i << " " << j << " " << R[j] << endl);
      addedBooks.pb(i);
      for(auto j : RG[i]) {
        depAv[j] -= 1;
        if(depAv[j] == 0) {
          DB(cerr << "Allow " << j << endl);
          addBook(j);
        }
      }
    };
    for(auto j : NX) addBook(j);

    while(!books.empty() && j >= 0) {
      auto it = books.upper_bound(R[j]);
      if(it == begin(books)) j -= 1;
      else {
        it = prev(it); auto p = *it; books.erase(it);
        A[UF.find(i)][j].pb(mt(Y(p), X(p))); rdelta[j] += X(p); R[j] -= X(p);
        addBookDeps(Y(p));
      }
    }

    if(books.empty() && ok2) {
      X[UF.find(i)] = NX;
      for(auto j : addedBooks) used[j] = 1;
      avTime -= depCost[i]; score += depWeight[i];
    } else { // revert, mark i invalid
      DB(cerr << "# Revert" << endl);
      valid[i] = false;
      for(auto p : rdelta) R[X(p)] += Y(p);
      A[UF.find(i)] = OLDA;
      for(auto p : OLDA){
        for(auto q : Y(p)) {
          R[X(p)] -= Y(q);
        }
      }
    }

    curTime += 1;
    for(auto k : comps[UF.find(i)]) depUpdate(k);
  }
}

//------------------------------------------------------------------------------

int main(int, char**){
  ios::sync_with_stdio(false);
  readInput();

  // ---

  bool isType4 = true;
  FOR(i, m) if(G[i].size() > 1 || RG[i].size() > 1) isType4 = false;

  bool isType3 = true;
  FOR(i, m) if(T[i] == 2) isType3 = false;

  // ---

  initSolution();
  solve();
  printSolution();
  DB(cerr << "Score: " << score << endl);

  return 0;
}