English · Original
Chinese · Translation
Formal · Original
You are given a set of integer numbers, initially it is empty. You should perform _n_ queries.
There are three different types of queries:
* _1_ _l_ _r_ — Add all missing numbers from the interval \[_l_, _r_\]
* _2_ _l_ _r_ — Remove all present numbers from the interval \[_l_, _r_\]
* _3_ _l_ _r_ — Invert the interval \[_l_, _r_\] — add all missing and remove all present numbers from the interval \[_l_, _r_\]
After each query you should output _MEX_ of the set — the smallest positive (_MEX_ ≥ 1) integer number which is not presented in the set.
## Input
The first line contains one integer number _n_ (1 ≤ _n_ ≤ 105).
Next _n_ lines contain three integer numbers _t_, _l_, _r_ (1 ≤ _t_ ≤ 3, 1 ≤ _l_ ≤ _r_ ≤ 1018) — type of the query, left and right bounds.
## Output
Print _MEX_ of the set after each query.
[samples]
## Note
Here are contents of the set after each query in the first example:
1. {3, 4} — the interval \[3, 4\] is added
2. {1, 2, 5, 6} — numbers {3, 4} from the interval \[1, 6\] got deleted and all the others are added
3. {5, 6} — numbers {1, 2} got deleted
[{"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}] 被删除 "}]}
**Definitions**
Let $ n \in \mathbb{Z} $ be the number of queries.
Let $ S \subseteq \mathbb{Z}^+ $ be the dynamic set of integers, initially $ S = \emptyset $.
Let 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} $.
**Operations**
For each query $ (t, l, r) $:
- If $ t = 1 $: Add all integers in $ [l, r] $ to $ S $:
$$
S \leftarrow S \cup \{ x \in \mathbb{Z} \mid l \leq x \leq r \}
$$
- If $ t = 2 $: Remove all integers in $ [l, r] $ from $ S $:
$$
S \leftarrow S \setminus \{ x \in \mathbb{Z} \mid l \leq x \leq r \}
$$
- If $ t = 3 $: Toggle all integers in $ [l, r] $:
$$
S \leftarrow S \oplus \{ x \in \mathbb{Z} \mid l \leq x \leq r \}
$$
(where $ \oplus $ denotes symmetric difference)
**Objective**
After each query, compute the MEX of $ S $:
$$
\text{MEX}(S) = \min \left( \mathbb{Z}^+ \setminus S \right)
$$
Output $ \text{MEX}(S) $ after each of the $ n $ queries.
API Response (JSON)
{
"problem": {
"name": "F. MEX Queries",
"description": {
"content": "You are given a set of integer numbers, initially it is empty. You should perform _n_ queries. There are three different types of queries: * _1_ _l_ _r_ — Add all missing numbers from the interval",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF817F"
},
"statements": [
{
"statement_type": "Markdown",
"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...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "[{\"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]）...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**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, ...",
"is_translate": false,
"language": "Formal"
}
]
}