{"raw_statement":[{"iden":"statement","content":"You are given a set of integer numbers, initially it is empty. You should perform _n_ queries.\n\nThere are three different types of queries:\n\n*   _1_ _l_ _r_ — Add all missing numbers from the interval \\[_l_, _r_\\]\n*   _2_ _l_ _r_ — Remove all present numbers from the interval \\[_l_, _r_\\]\n*   _3_ _l_ _r_ — Invert the interval \\[_l_, _r_\\] — add all missing and remove all present numbers from the interval \\[_l_, _r_\\]\n\nAfter each query you should output _MEX_ of the set — the smallest positive (_MEX_  ≥ 1) integer number which is not presented in the set."},{"iden":"input","content":"The first line contains one integer number _n_ (1 ≤ _n_ ≤ 105).\n\nNext _n_ lines contain three integer numbers _t_, _l_, _r_ (1 ≤ _t_ ≤ 3, 1 ≤ _l_ ≤ _r_ ≤ 1018) — type of the query, left and right bounds."},{"iden":"output","content":"Print _MEX_ of the set after each query."},{"iden":"examples","content":"Input\n\n3\n1 3 4\n3 1 6\n2 1 3\n\nOutput\n\n1\n3\n1\n\nInput\n\n4\n1 1 3\n3 5 6\n2 4 4\n3 1 6\n\nOutput\n\n4\n4\n4\n1"},{"iden":"note","content":"Here are contents of the set after each query in the first example:\n\n1.  {3, 4} — the interval \\[3, 4\\] is added\n2.  {1, 2, 5, 6} — numbers {3, 4} from the interval \\[1, 6\\] got deleted and all the others are added\n3.  {5, 6} — numbers {1, 2} got deleted"}],"translated_statement":"[{\"iden\":\"statement\",\"content\":\"你有一个初始为空的整数集合。你需要执行 #cf_span[n] 次查询。\\n\\n共有三种不同类型的查询：\\n\\n每次查询后，你需要输出该集合的 _MEX_ —— 即最小的正整数（_MEX_ #cf_span[ ≥ 1]），该数不在集合中。\\n\\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 10^5]）。\\n\\n接下来 #cf_span[n] 行每行包含三个整数 #cf_span[t, l, r]（#cf_span[1 ≤ t ≤ 3, 1 ≤ l ≤ r ≤ 10^{18}]），分别表示查询类型、左边界和右边界。\\n\\n请在每次查询后输出集合的 _MEX_。\\n\\n以下是第一个示例中每次查询后集合的内容：\\n\\n\"},{\"iden\":\"input\",\"content\":\"第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 10^5]）。接下来 #cf_span[n] 行每行包含三个整数 #cf_span[t, l, r]（#cf_span[1 ≤ t ≤ 3, 1 ≤ l ≤ r ≤ 10^{18}]），分别表示查询类型、左边界和右边界。\"},{\"iden\":\"output\",\"content\":\"请在每次查询后输出集合的 _MEX_。\"},{\"iden\":\"examples\",\"content\":\"输入\\n3\\n1 3 4\\n3 1 6\\n2 1 3\\n输出\\n1\\n3\\n1\\n\\n输入\\n4\\n1 1 3\\n3 5 6\\n2 4 4\\n3 1 6\\n输出\\n4\\n4\\n4\\n1\"},{\"iden\":\"note\",\"content\":\"以下是第一个示例中每次查询后集合的内容：  #cf_span[{3, 4}] —— 区间 #cf_span[[3, 4]] 被加入  #cf_span[{1, 2, 5, 6}] —— 区间 #cf_span[[1, 6]] 中的数字 #cf_span[{3, 4}] 被删除，其余数字被加入  #cf_span[{5, 6}] —— 数字 #cf_span[{1, 2}] 被删除 \"}]}","sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of queries.  \nLet $ S \\subseteq \\mathbb{Z}^+ $ be the dynamic set of integers, initially $ S = \\emptyset $.  \nLet each query be a triple $ (t, l, r) \\in \\{1,2,3\\} \\times \\mathbb{Z} \\times \\mathbb{Z} $ with $ 1 \\leq l \\leq r \\leq 10^{18} $.\n\n**Operations**  \nFor each query $ (t, l, r) $:  \n- If $ t = 1 $: Add all integers in $ [l, r] $ to $ S $:  \n  $$\n  S \\leftarrow S \\cup \\{ x \\in \\mathbb{Z} \\mid l \\leq x \\leq r \\}\n  $$  \n- If $ t = 2 $: Remove all integers in $ [l, r] $ from $ S $:  \n  $$\n  S \\leftarrow S \\setminus \\{ x \\in \\mathbb{Z} \\mid l \\leq x \\leq r \\}\n  $$  \n- If $ t = 3 $: Toggle all integers in $ [l, r] $:  \n  $$\n  S \\leftarrow S \\oplus \\{ x \\in \\mathbb{Z} \\mid l \\leq x \\leq r \\}\n  $$  \n  (where $ \\oplus $ denotes symmetric difference)\n\n**Objective**  \nAfter each query, compute the MEX of $ S $:  \n$$\n\\text{MEX}(S) = \\min \\left( \\mathbb{Z}^+ \\setminus S \\right)\n$$  \nOutput $ \\text{MEX}(S) $ after each of the $ n $ queries.","simple_statement":null,"has_page_source":false}