{"raw_statement":[{"iden":"statement","content":"In one well-known algorithm of finding the _k_\\-th order statistics we should divide all elements into groups of five consecutive elements and find the median of each five. A median is called the middle element of a sorted array (it's the third largest element for a group of five). To increase the algorithm's performance speed on a modern video card, you should be able to find a sum of medians in each five of the array.\n\nA _sum of medians_ of a sorted _k_\\-element set _S_ = {_a_1, _a_2, ..., _a__k_}, where _a_1 < _a_2 < _a_3 < ... < _a__k_, will be understood by as\n\nThe operator stands for taking the remainder, that is stands for the remainder of dividing _x_ by _y_.\n\nTo organize exercise testing quickly calculating _the sum of medians_ for a changing set was needed."},{"iden":"input","content":"The first line contains number _n_ (1 ≤ _n_ ≤ 105), the number of operations performed.\n\nThen each of _n_ lines contains the description of one of the three operations:\n\n*   _add _x__ — add the element _x_ to the set;\n*   _del _x__ — delete the element _x_ from the set;\n*   _sum_ — find the _sum of medians_ of the set.\n\nFor any _add _x__ operation it is true that the element _x_ is not included in the set directly before the operation.\n\nFor any _del _x__ operation it is true that the element _x_ is included in the set directly before the operation.\n\nAll the numbers in the input are positive integers, not exceeding 109."},{"iden":"output","content":"For each operation _sum_ print on the single line _the sum of medians_ of the current set. If the set is empty, print 0.\n\nPlease, do not use the _%lld_ specificator to read or write 64-bit integers in C++. It is preferred to use the _cin_, _cout_ streams (also you may use the _%I64d_ specificator)."},{"iden":"examples","content":"Input\n\n6\nadd 4\nadd 5\nadd 1\nadd 2\nadd 3\nsum\n\nOutput\n\n3\n\nInput\n\n14\nadd 1\nadd 7\nadd 2\nadd 5\nsum\nadd 6\nadd 8\nadd 9\nadd 3\nadd 4\nadd 10\nsum\ndel 1\nsum\n\nOutput\n\n5\n11\n13"}],"translated_statement":[{"iden":"statement","content":"在一种著名的寻找第 #cf_span[k] 小元素的算法中，我们需要将所有元素划分为每五个连续元素一组，并求出每组的中位数。中位数是指排序后数组的中间元素（对于五个元素的组，它是第三大的元素）。为了提高该算法在现代显卡上的运行速度，你需要能够快速计算出数组中每五个元素的中位数之和。\n\n对于一个已排序的 #cf_span[k] 元素集合 #cf_span[S = {a1, a2, ..., ak}]，其中 #cf_span[a1 < a2 < a3 < ... < ak]，其 _中位数之和_ 定义为：\n\n其中  操作符表示取余，即  表示 #cf_span[x] 除以 #cf_span[y] 的余数。\n\n为了快速进行练习测试，需要能够高效计算动态变化集合的 _中位数之和_。\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 10^5]），表示执行的操作数量。\n\n接下来的 #cf_span[n] 行，每行描述以下三种操作之一：\n\n对于任何 _add #cf_span[x]_ 操作，元素 #cf_span[x] 在操作前不在集合中。\n\n对于任何 _del #cf_span[x]_ 操作，元素 #cf_span[x] 在操作前在集合中。\n\n输入中的所有数字均为不超过 #cf_span[10^9] 的正整数。\n\n对于每个 _sum_ 操作，请在单独一行输出当前集合的 _中位数之和_。如果集合为空，请输出 0。\n\n请勿在 C++ 中使用 _%lld_ 标识符读写 64 位整数。推荐使用 _cin_、_cout_ 流（也可使用 _%I64d_ 标识符）。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 10^5]），表示执行的操作数量。接下来的 #cf_span[n] 行，每行描述以下三种操作之一：\n_add #cf_span[x]_ — 将元素 #cf_span[x] 加入集合；\n_del #cf_span[x]_ — 将元素 #cf_span[x] 从集合中删除；\n_sum_ — 计算集合的 _中位数之和_。\n对于任何 _add #cf_span[x]_ 操作，元素 #cf_span[x] 在操作前不在集合中。\n对于任何 _del #cf_span[x]_ 操作，元素 #cf_span[x] 在操作前在集合中。\n输入中的所有数字均为不超过 #cf_span[10^9] 的正整数。"},{"iden":"output","content":"对于每个 _sum_ 操作，请在单独一行输出当前集合的 _中位数之和_。如果集合为空，请输出 0。\n请勿在 C++ 中使用 _%lld_ 标识符读写 64 位整数。推荐使用 _cin_、_cout_ 流（也可使用 _%I64d_ 标识符）。"},{"iden":"examples","content":"输入：\n6\nadd 4\nadd 5\nadd 1\nadd 2\nadd 3\nsum\n输出：\n3\n\n输入：\n14\nadd 1\nadd 7\nadd 2\nadd 5\nsum\nadd 6\nadd 8\nadd 9\nadd 3\nadd 4\nadd 10\nsum\ndel 1\nsum\n输出：\n5\n11\n13"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ S \\subseteq \\mathbb{Z}^+ $ be a dynamic multiset (initially empty).  \nLet $ |S| = k $, and let $ S = \\{a_1, a_2, \\dots, a_k\\} $ with $ a_1 < a_2 < \\dots < a_k $ be the sorted representation of $ S $.  \n\nFor a sorted set $ S $ of size $ k $, the **sum of medians** is defined as:  \n$$\n\\sum_{i=1}^{\\left\\lceil \\frac{k}{5} \\right\\rceil} a_{5(i-1) + 3}\n$$  \nwhere the $ i $-th group of five consists of elements at positions $ 5(i-1)+1 $ to $ 5(i-1)+5 $, and the median of each group is the 3rd element (i.e., index $ 5(i-1)+3 $) in the sorted group.  \nIf a group has fewer than 5 elements, it is still considered, and its median is the element at position $ \\min(3, \\text{group size}) $ within the group (i.e., the 3rd element if it exists, otherwise the last).\n\n**Operations**  \nGiven $ n \\in \\mathbb{Z} $, $ 1 \\le n \\le 10^5 $, perform $ n $ operations on $ S $:  \n- `add x`: Insert $ x \\in \\mathbb{Z}^+ $, $ x \\le 10^9 $, into $ S $ (guaranteed not present).  \n- `del x`: Remove $ x \\in \\mathbb{Z}^+ $, $ x \\le 10^9 $, from $ S $ (guaranteed present).  \n- `sum`: Compute and output the **sum of medians** of the current $ S $; if $ S = \\emptyset $, output 0.\n\n**Objective**  \nFor each `sum` operation, output the sum of medians of the current sorted set $ S $, computed as described.","simple_statement":null,"has_page_source":false}