Замовлення Айсберг
Обмеження на час виконання 1 секунда
Обмеження на використання пам'яті 128 мегабайтів
Ви працюєте на біржі Метагонія. Нещодавно торговці в Метагонії дізналися про заявки айсберга, що використовуються на Лондонській фондовій біржі, і попросили вашого роботодавця додати таку функціональність. Фондова біржа - це фінансовий інститут, який отримує замовлення і генерує угоди. Заявка айсберга - це п'ятірка цілих чисел (**ID**, **T**, **P**, **V**, **TV**). Кожна заявка має унікальний ідентифікатор **ID**, тип **T** (або **BUY** = **1**, або **SELL** = **2**), ціну **P**, загальний залишковий обсяг **V** і видимий обсяг **TV**. Для кожної заявки також відстежується її поточний обсяг **CV** і пріоритет **PR**. Існує також глобальний лічильник пріоритетів обміну **GP**. Заявка додається до набору заявок біржі. Торги, що генеруються на біржі, представляють собою чотири цілі числа (**BUY-ID**, **SELL-ID**, **P**, **V**). Кожна угода містить **BUY-ID** і **SELL-ID** - ідентифікатори відповідних **КУПИТИ** і **ПРОДАТИ** замовлень, торгову ціну **P** і обсяг торгів **V**. Коли заявка виставляється на торги, вона зіставляється із заявками, що вже є в реєстрі. Це відбувається наступним чином. Нехай отримано замовлення **a**, у якого `T[a]` = **SELL**. Серед усіх заявок, виставлених на торги, ми шукаємо заявку **b**, таку що `T[b]` = **BUY** і `P[b]` ≥ `P[a]`. Ми вибираємо таку заявку **b**, яка має найбільшу ціну, а якщо таких кілька - то з найменшим пріоритетом. Якщо така заявка **b** існує, то **a** генерує торгову угоду **t**, у якої `BUY-ID[t]` = `ID[b]` і `SELL-ID[t]` = `ID[a]` за ціною `P[t]` = `P[b]` обсягом `V[t]` = min(`V[a]`,`CV[b]`). Значення `V[a]`, `V[b]` і `CV[b]` зменшуються на обсяг угоди. Якщо після цього `V[b]` = **0**, то заявка **b** видаляється з реєстру заявок. Якщо `CV[b]` = **0** (але `V[b]` > **0**), то встановлюємо поточний обсяг заявки **b** рівним `CV[b]` = min(`V[b]`, `TV[b]`), встановлюємо `PR[b]` = **GP**, і збільшуємо **GP**. Продовжуємо операції вибору **b** і генерування торгів, поки не стане або `V[a]` = **0**, або не залишиться таких заявок **b** в реєстрі, що задовольняють умові можливості торгів. У цьому випадку ми додаємо замовлення a до книги замовлень з `CV[a]` = min(`V[a]`, `TV[a]`) і `PR[a]` = **GP**, а потім збільшуємо **GP**. Коли процес зіставлення замовлення **a** завершено з кількома угодами між однією парою замовлень **a** і **b** (і їх може бути багато!), вони всі об'єднуються в одну угоду з обсягом, рівним сумі обсягів окремих угод. Якщо `T[a]` = **BUY**, ми шукаємо замовлення **b** з `T[b]` = **SELL** і `P[b]` ≤ `P[a]` і вибираємо таке замовлення **b** з найменшою ціною і найменшим пріоритетом серед них. Решта процесу зіставлення описана вище, з угодами, що мають `BUY-ID[t]` = `ID[a]`, `SELL-ID[t]` = `ID[b]`, `P[t]` = `P[b]`, і `V[t]` = min(`V[a]`,`CV[b]`). Спочатку книга замовлень порожня. Вам надано кілька замовлень, які надходять на біржу одне за одним. Вам потрібно надрукувати згенеровані угоди і стан книги замовлень після обробки всіх замовлень. Підказка: Пріоритет і **GP** введені в умові задачі лише для формального опису алгоритму. Реальна реалізація не повинна відстежувати пріоритет. Зазвичай біржа просто веде список замовлень кожного типу за кожною ціною в своїй книзі замовлень, упорядкований за пріоритетом. #### Вхідні дані Перша рядок містить кількість заявок **n** (**1** ≤ **n** ≤ **50000**). Кожен з наступних **n** рядків представляє заявку. Кожна заявка задається п'ятіркою **ID T P V TV**, де **1** ≤ **ID** ≤ **1000000**, **T** = **1** для **BUY** і **T** = **2** для **SELL**, **1** ≤ **P** ≤ **100000** і **1** ≤ **TV** ≤ **V** ≤ `10^9`. #### Вихідні дані Для кожного замовлення надрукуйте всі угоди, згенеровані обробкою цього замовлення, у порядку зростання пар (**BUY-ID**, **SELL-ID**), кожну угоду на окремому рядку. Кожна угода повинна бути надрукована як пробілом розділена четвірка цілих чисел **BUY-ID SELL-ID P V**. Гарантовано, що загальна кількість угод не перевищить **100000**. Надрукуйте порожній рядок після всіх угод, за яким слідує книга замовлень. Кожне замовлення, яке все ще є в книзі, повинно бути надруковано як пробілом розділена шістка **ID T P V TV CV**, відсортована спочатку за **P**, а потім за **PR**. #### Пояснення У прикладі перші чотири заявки мають **T** = **BUY**. Припускаючи, що на початку торгів **GP** дорівнювало **1**, після отримання цих заявок реєстр виглядає наступним чином, упорядкований за правилами відповідності з умови задачі для `T[b]` = **BUY** (спочатку за спаданням ціни, потім за зростанням пріоритету):  П'ята заявка (`ID[a]` = **4321**) має `T[a]` = **SELL**, `P[a]` = **99** і `V[a]` = **125** і може бути зіставлена з усіма чотирма заявками, наведеними в таблиці вище. Спочатку вона зіставляється двічі із заявкою **1111** з найвищою ціною **101** на загальний обсяг угоди **30**, видаляє її з книги замовлень, збільшує **GP** до **6** в процесі, і зменшує `V[a]` до **95**. Потім є три інші заявки за ціною **100**. Один прохід зіставлення через них генерує три угоди на загальний обсяг **85** (обсяг **20** із заявкою **42**, обсяг **50** із заявкою **239**, видаляє її з книги, обсяг **15** із заявкою **1234**), збільшує **GP** до **8**, і зменшує `V[a]` до **10**. Залишилися заявки в книзі показані нижче:  Останнє зіставлення із заявкою **42** генерує угоду з обсягом **10** (на загальний обсяг **30** для зіставлень із заявкою **42**) і заявка **4321** завершена (`V[a]` = **0**). Чотири відповідні загальні угоди для заявки **4321** надруковані у вихідних даних прикладу. Залишилася книга замовлень:  Шоста заявка **BUY** (з **ID** = **5678**) додається до книги замовлень (**GP** стає **9**):  Остання, сьома заявка (з **ID** = **8765**), може бути зіставлена лише із заявкою **5678** через цінову умову, генерує угоду з обсягом **30**, заявка **5678** видаляється з книги замовлень, тоді як заявка 8765 додається. Тепер книга замовлень має як **BUY**, так і **SELL** заявки: 
Приклади
Вхідні дані #1
Відповідь #1
Відправки 2
Коефіцієнт прийняття 100%