#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef long double ld; typedef pair ii; typedef vector vi; typedef vector vvi; typedef vector vii; #define x first #define y second #define pb push_back #define eb emplace_back #define rep(i,a,b) for(auto i=(a); i<(b); ++i) #define REP(i,n) rep(i,0,n) #define all(v) (v).begin(), (v).end() #define rs resize #define DBG(x) cerr << __LINE__ << ": " << #x << " = " << (x) << endl const ld PI = acos(-1.0); template using min_queue = priority_queue, greater>; template int sz(const T &x) { return (int) x.size(); // copy the ampersand(&)! } // START OF ACTUAL PROGRAM, START READING HERE struct BIT { int n; vi A; BIT(int _n) : n(_n), A(_n+1, 0) {} BIT(vi &v) : n(sz(v)), A(1) { for (auto x:v) A.pb(x); for (int i=1, j; j=i&-i, i<=n; i++) if (i+j <= n) A[i+j] += A[i]; } void update(int i, ll v) { while (i <= n) A[i] += v, i+= i&-i; } ll query(int i) { ll v = 0; while (i) v += A[i], i -= i&-i; return v; } }; void run() { ll n; cin >> n; vi P(n), A(n); vector S(n), T(n); set Ps; unordered_map Pm; for (ll i = 0; i < n; i++) { cin >> S[i] >> T[i] >> P[i] >> A[i]; Ps.insert(P[i]); } ll np = 0; for (ll p : Ps) { np++; Pm[p] = np; } for (ll i = 0; i < n; i++) { P[i] = Pm[P[i]]; } priority_queue>> Bq, Sq; BIT Bb(np), Sb(np); vector> R; for (ll i = 0; i < n; i++) { if (S[i][0] == 'b') { if (T[i][0] == 'n' || Sb.query(P[i]) >= A[i]) { Bq.push({P[i], {-i, A[i]}}); Bb.update(P[i], A[i]); } } else { if (T[i][0] == 'n' || Bb.query(np)-Bb.query(P[i]-1) >= A[i]) { Sq.push({-P[i], {-i, A[i]}}); Sb.update(P[i], A[i]); } } while (!Bq.empty() && !Sq.empty() && Bq.top().x >= -Sq.top().x) { auto b = Bq.top(); Bq.pop(); auto s = Sq.top(); Sq.pop(); ll a = min(b.y.y, s.y.y); R.pb({{-b.y.x, -s.y.x}, a}); Bb.update(b.x, -a); Sb.update(-s.x, -a); if (b.y.y > a) Bq.push({b.x, {b.y.x, b.y.y-a}}); if (s.y.y > a) Sq.push({s.x, {s.y.x, s.y.y-a}}); } } cout << R.size() << endl; for (auto r : R) { cout << r.x.y+1 << " " << r.x.x+1 << " " << r.y << endl; } } signed main() { // DON'T MIX "scanf" and "cin"! ios_base::sync_with_stdio(false); cin.tie(NULL); cout << fixed << setprecision(20); run(); return 0; }