#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define FI( type) vector<type>::iterator
#define isBetween( A,B,C) (((A <= B) and (B <= C)))
using namespace std;
typedef unsigned uint;
typedef vector<int> i_vec ;
typedef vector< vector<int> > iv_vec ;
void Begin();
struct frend
{
int food, num, start, end;
frend( int beg, int last, int f, int n)
:food( f), num( n), start( beg), end( last) {}
frend(){}
inline bool operator() (const frend uno, const frend duo)
{
return ( uno.food < duo.food );
}
};
typedef vector <frend> f_vec;
struct Dorm
{
uint foodNeed, numDays;
iv_vec action;
i_vec food_per_day;
FI( frend) it;
f_vec Berland;
public:
Dorm (int n, int f)
:foodNeed( f), numDays( n)
{
food_per_day.resize( n+1 );
for ( uint i=0; i < (uint) n ; ++i )
scanf( "%d", &food_per_day[i] ), food_per_day[i] -= foodNeed ;//food for Vasya is stored
}
void Print( int );
void Solve( );
void HandleFood( uint&, uint, int&, int & );
};
int main()
{
int n, v, m, t(1), k(0);
//Begin();
scanf( "%d%d", &n, &v );
Dorm Vasya( n,v );
for ( scanf("%d", &m); m--; )
{
scanf( "%d%d%d", &n, &v, &t );
Vasya.Berland.push_back( frend( n, v, t, ++k ) );
}
Vasya.Solve();
return 0;
}
void Dorm::Solve()
{
stable_sort( Berland.begin(), Berland.end(), Berland.back() );//sort in order of lowest need for food to highest
uint Pop(0);
for ( uint p = 0, l(0), prev(0); p < numDays; ++p, l = 0)
{
i_vec row;
l = food_per_day[p], row.push_back(0);
for ( it = Berland.begin(); it != Berland.end() and (( food_per_day[p] - it->food ) >= 0); ++it )
{
if ( isBetween(it->start, int(p+1), it->end) )//Are you staying with me this day?
{
food_per_day[p] -= it->food, ++Pop;//increase popularity
++( row.front() );//number Friends fed
row.push_back( it->num ) ;//index of friend
}
}
HandleFood(prev, l, food_per_day[p], food_per_day[p+1]);
action.push_back(row);
}
Print(Pop);
}
void Dorm::Print(int P)
{
printf( "%d\n", P );
for ( iv_vec::iterator it = action.begin(); it !=action.end(); ++it )
{
for ( i_vec::iterator pi = it->begin(); pi != it->end(); ++pi )
printf( "%d ", *pi );
puts( "" );
}
}
void Dorm::HandleFood(uint &left2, uint tot, int &left1 , int &next)
{
if ( left2 > ( tot -= left1 ) )//did not finish leftover from yesterday?
left1 -= ( left2 - tot );//Remove the amount not finished
next += left1;//add whatever is left from today to tomorrow's food
left2 = left1;//Amount left for today is stored
}
void Begin()
{
freopen("input.txt","r", stdin);
freopen("output.txt","w", stdout);
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8Y3N0ZGlvPgojaW5jbHVkZSA8Y3N0cmluZz4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2RlZmluZSBGSSggdHlwZSkgdmVjdG9yPHR5cGU+OjppdGVyYXRvcgojZGVmaW5lIGlzQmV0d2VlbiggQSxCLEMpICgoKEEgPD0gQikgYW5kIChCIDw9IEMpKSkKCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0eXBlZGVmIHVuc2lnbmVkIHVpbnQ7CnR5cGVkZWYgdmVjdG9yPGludD4gaV92ZWMgOwp0eXBlZGVmIHZlY3RvcjwgdmVjdG9yPGludD4gPiBpdl92ZWMgOwoKdm9pZCBCZWdpbigpOwoKc3RydWN0IGZyZW5kCnsKICAgaW50IGZvb2QsIG51bSwgc3RhcnQsIGVuZDsKICAgZnJlbmQoIGludCBiZWcsIGludCBsYXN0LCBpbnQgZiwgaW50IG4pCiAgIDpmb29kKCBmKSwgbnVtKCBuKSwgc3RhcnQoIGJlZyksIGVuZCggbGFzdCkge30KICAgZnJlbmQoKXt9CiAgIAogICBpbmxpbmUgYm9vbCBvcGVyYXRvcigpIChjb25zdCBmcmVuZCB1bm8sIGNvbnN0IGZyZW5kIGR1bykKICAgewogICAgICByZXR1cm4gKCB1bm8uZm9vZCA8IGR1by5mb29kICk7IAogICB9Cn07Cgp0eXBlZGVmIHZlY3RvciA8ZnJlbmQ+IGZfdmVjOwoKc3RydWN0IERvcm0KewogICB1aW50IGZvb2ROZWVkLCBudW1EYXlzOwogICBpdl92ZWMgYWN0aW9uOwogICBpX3ZlYyBmb29kX3Blcl9kYXk7CiAgIEZJKCBmcmVuZCkgaXQ7CiAgIGZfdmVjIEJlcmxhbmQ7CiAgIApwdWJsaWM6ICAgCiAgIERvcm0gKGludCBuLCBpbnQgZikKICAgOmZvb2ROZWVkKCBmKSwgbnVtRGF5cyggbikKICAgewogICAgICBmb29kX3Blcl9kYXkucmVzaXplKCBuKzEgKTsKICAgICAgCiAgICAgIGZvciAoIHVpbnQgaT0wOyBpIDwgKHVpbnQpIG4gOyArK2kgKQogICAgIHNjYW5mKCAiJWQiLCAmZm9vZF9wZXJfZGF5W2ldICksIGZvb2RfcGVyX2RheVtpXSAtPSBmb29kTmVlZCA7Ly9mb29kIGZvciBWYXN5YSBpcyBzdG9yZWQKICAgfQogICAKICAgdm9pZCBQcmludCggaW50ICk7CiAgIHZvaWQgU29sdmUoICk7CiAgIHZvaWQgSGFuZGxlRm9vZCggdWludCYsIHVpbnQsIGludCYsIGludCAmICk7Cn07CgoKaW50IG1haW4oKQp7CiAgIGludCBuLCB2LCBtLCB0KDEpLCBrKDApOwogICAKICAgLy9CZWdpbigpOwogICAKICAgc2NhbmYoICIlZCVkIiwgJm4sICZ2ICk7CiAgIERvcm0JVmFzeWEoIG4sdiApOwogICAKICAgZm9yICggc2NhbmYoIiVkIiwgJm0pOyBtLS07ICkKICAgewogICAgICBzY2FuZiggIiVkJWQlZCIsICZuLCAmdiwgJnQgKTsKICAgICAgVmFzeWEuQmVybGFuZC5wdXNoX2JhY2soIGZyZW5kKCBuLCB2LCB0LCArK2sgKSApOwogICB9CiAgIAogICBWYXN5YS5Tb2x2ZSgpOwogICAKICAgcmV0dXJuIDA7Cn0KCnZvaWQgRG9ybTo6U29sdmUoKQp7CiAgIHN0YWJsZV9zb3J0KCBCZXJsYW5kLmJlZ2luKCksIEJlcmxhbmQuZW5kKCksIEJlcmxhbmQuYmFjaygpICk7Ly9zb3J0IGluIG9yZGVyIG9mIGxvd2VzdCBuZWVkIGZvciBmb29kIHRvIGhpZ2hlc3QKICAgdWludCBQb3AoMCk7CiAgIAogICBmb3IgKCB1aW50IHAgPSAwLCBsKDApLCBwcmV2KDApOyBwIDwgbnVtRGF5czsgKytwLCBsID0gMCkKICAgewogICAgICBpX3ZlYyByb3c7CiAgICAgIGwgPSBmb29kX3Blcl9kYXlbcF0sIHJvdy5wdXNoX2JhY2soMCk7CiAgICAgIGZvciAoIGl0ID0gQmVybGFuZC5iZWdpbigpOyBpdCAhPSBCZXJsYW5kLmVuZCgpIGFuZCAoKCBmb29kX3Blcl9kYXlbcF0gLSBpdC0+Zm9vZCApID49IDApOyArK2l0ICkKICAgICAgewoJIGlmICggaXNCZXR3ZWVuKGl0LT5zdGFydCwgaW50KHArMSksIGl0LT5lbmQpICkvL0FyZSB5b3Ugc3RheWluZyB3aXRoIG1lIHRoaXMgZGF5PwoJIHsKCSAgICBmb29kX3Blcl9kYXlbcF0gLT0gaXQtPmZvb2QsICsrUG9wOy8vaW5jcmVhc2UgcG9wdWxhcml0eQoJICAgICsrKCByb3cuZnJvbnQoKSApOy8vbnVtYmVyIEZyaWVuZHMgZmVkCgkgICAgcm93LnB1c2hfYmFjayggaXQtPm51bSApIDsvL2luZGV4IG9mIGZyaWVuZAoJIH0KICAgICAgfQogICAgICAKICAgICAgSGFuZGxlRm9vZChwcmV2LCBsLCBmb29kX3Blcl9kYXlbcF0sIGZvb2RfcGVyX2RheVtwKzFdKTsKICAgICAgYWN0aW9uLnB1c2hfYmFjayhyb3cpOwogICB9CiAgIAogICBQcmludChQb3ApOwp9Cgp2b2lkIERvcm06OlByaW50KGludCBQKQp7CiAgIHByaW50ZiggIiVkXG4iLCBQICk7CiAgIAogICBmb3IgKCBpdl92ZWM6Oml0ZXJhdG9yIGl0ID0gYWN0aW9uLmJlZ2luKCk7IGl0ICE9YWN0aW9uLmVuZCgpOyArK2l0ICkKICAgewogICAgICBmb3IgKCBpX3ZlYzo6aXRlcmF0b3IgcGkgPSBpdC0+YmVnaW4oKTsgcGkgIT0gaXQtPmVuZCgpOyArK3BpICkKCSBwcmludGYoICIlZCAiLCAqcGkgKTsKICAgICAgCiAgICAgIHB1dHMoICIiICk7CiAgIH0KfQoKdm9pZCBEb3JtOjpIYW5kbGVGb29kKHVpbnQgJmxlZnQyLCB1aW50IHRvdCwgaW50ICZsZWZ0MSAsIGludCAmbmV4dCkKewogICBpZiAoIGxlZnQyID4gKCB0b3QgLT0gbGVmdDEgKSApLy9kaWQgbm90IGZpbmlzaCBsZWZ0b3ZlciBmcm9tIHllc3RlcmRheT8KICAgICAgbGVmdDEgLT0gKCBsZWZ0MiAtIHRvdCApOy8vUmVtb3ZlIHRoZSBhbW91bnQgbm90IGZpbmlzaGVkCiAgIG5leHQgKz0gbGVmdDE7Ly9hZGQgd2hhdGV2ZXIgaXMgbGVmdCBmcm9tIHRvZGF5IHRvIHRvbW9ycm93J3MgZm9vZAogICBsZWZ0MiA9IGxlZnQxOy8vQW1vdW50IGxlZnQgZm9yIHRvZGF5IGlzIHN0b3JlZAp9Cgp2b2lkIEJlZ2luKCkKewogICBmcmVvcGVuKCJpbnB1dC50eHQiLCJyIiwgc3RkaW4pOwogICBmcmVvcGVuKCJvdXRwdXQudHh0IiwidyIsIHN0ZG91dCk7Cn0=