import java.util.PriorityQueue private class BIT(val n: Int) { private val x = LongArray(n) fun add(pos:Int, value: Long) { var ppos = pos while (ppos < n) { x[ppos] += value ppos = ppos or (ppos + 1) } } fun get(pos: Int): Long { var ans: Long = 0 var ppos = pos while (ppos != -1) { ans += x[ppos] ppos = (ppos and (ppos + 1)) - 1 } return ans } fun get(l:Int, r:Int) = get(r - 1) - get(l - 1) } data class Order(val index: Int, val isSell: Boolean, val isNormal: Boolean, var price: Int,var size: Int) fun main() { val n = readInt() val orders = List(n) { val d = readStrings() Order(it, d[0] == "sell", d[1] == "normal", d[2].toInt(), d[3].toInt()) } val prices = orders.map { it.price }.distinct().sorted() for (o in orders) { o.price = prices.binarySearch(o.price) } val bit = BIT(prices.size) val buy = PriorityQueue(compareByDescending { orders[it].price }.thenComparingInt { it }) val sell = PriorityQueue(compareBy { orders[it].price }.thenComparingInt { it }) val answer = mutableListOf>() fun match() { while (true) { val buyId = buy.peek() ?: return val sellId = sell.peek() ?: return if (orders[buyId].price >= orders[sellId].price) { val count = minOf(orders[buyId].size, orders[sellId].size) require(count > 0) answer.add(Triple(sellId, buyId, count)) orders[buyId].size -= count bit.add(orders[buyId].price, -count.toLong()) if (orders[buyId].size == 0) buy.poll() orders[sellId].size -= count bit.add(orders[sellId].price, -count.toLong()) if (orders[sellId].size == 0) sell.poll() } else { break } } } for (i in orders) { if (!i.isNormal) { if (i.isSell) { val p = orders[buy.peek() ?: continue].price if (i.price > p || bit.get(i.price, p + 1) < i.size) continue } else { val p = orders[sell.peek() ?: continue].price if (p > i.price || bit.get(p, i.price + 1) < i.size) continue } } bit.add(i.price, i.size.toLong()) (if (i.isSell) sell else buy).add(i.index) match() if (!i.isNormal) { require(i.size == 0) } } println(answer.size) for ((a, b, c) in answer) { println("${a+1} ${b+1} $c") } } private fun readInt() = readln().toInt() private fun readLongs() = readStrings().map { it.toLong() } private fun readStrings() = readln().split(" ") private fun readInts() = readStrings().map { it.toInt() }