{"raw_statement":[{"iden":"statement","content":"Anton likes to play chess. Also he likes to do programming. No wonder that he decided to attend chess classes and programming classes.\n\nAnton has _n_ variants when he will attend chess classes, _i_\\-th variant is given by a period of time (_l_1, _i_, _r_1, _i_). Also he has _m_ variants when he will attend programming classes, _i_\\-th variant is given by a period of time (_l_2, _i_, _r_2, _i_).\n\nAnton needs to choose **exactly one** of _n_ possible periods of time when he will attend chess classes and **exactly one** of _m_ possible periods of time when he will attend programming classes. He wants to have a rest between classes, so from all the possible pairs of the periods he wants to choose the one where the distance between the periods is maximal.\n\nThe distance between periods (_l_1, _r_1) and (_l_2, _r_2) is the minimal possible distance between a point in the first period and a point in the second period, that is the minimal possible |_i_ - _j_|, where _l_1 ≤ _i_ ≤ _r_1 and _l_2 ≤ _j_ ≤ _r_2. In particular, when the periods intersect, the distance between them is 0.\n\nAnton wants to know how much time his rest between the classes will last in the best case. Help Anton and find this number!"},{"iden":"input","content":"The first line of the input contains a single integer _n_ (1 ≤ _n_ ≤ 200 000) — the number of time periods when Anton can attend chess classes.\n\nEach of the following _n_ lines of the input contains two integers _l_1, _i_ and _r_1, _i_ (1 ≤ _l_1, _i_ ≤ _r_1, _i_ ≤ 109) — the _i_\\-th variant of a period of time when Anton can attend chess classes.\n\nThe following line of the input contains a single integer _m_ (1 ≤ _m_ ≤ 200 000) — the number of time periods when Anton can attend programming classes.\n\nEach of the following _m_ lines of the input contains two integers _l_2, _i_ and _r_2, _i_ (1 ≤ _l_2, _i_ ≤ _r_2, _i_ ≤ 109) — the _i_\\-th variant of a period of time when Anton can attend programming classes."},{"iden":"output","content":"Output one integer — the maximal possible distance between time periods."},{"iden":"examples","content":"Input\n\n3\n1 5\n2 6\n2 3\n2\n2 4\n6 8\n\nOutput\n\n3\n\nInput\n\n3\n1 5\n2 6\n3 7\n2\n2 4\n1 4\n\nOutput\n\n0"},{"iden":"note","content":"In the first sample Anton can attend chess classes in the period (2, 3) and attend programming classes in the period (6, 8). It's not hard to see that in this case the distance between the periods will be equal to 3.\n\nIn the second sample if he chooses any pair of periods, they will intersect. So the answer is 0."}],"translated_statement":[{"iden":"statement","content":"Anton 喜欢下棋，也喜欢编程。因此他决定参加棋类课程和编程课程。\n\nAnton 有 #cf_span[n] 种选择来参加棋类课程，第 #cf_span[i] 种选择由时间段 #cf_span[(l1, i, r1, i)] 给出。同时，他有 #cf_span[m] 种选择来参加编程课程，第 #cf_span[i] 种选择由时间段 #cf_span[(l2, i, r2, i)] 给出。\n\nAnton 需要从 #cf_span[n] 个可能的时间段中恰好选择一个来参加棋类课程，并从 #cf_span[m] 个可能的时间段中恰好选择一个来参加编程课程。他希望在课程之间休息，因此在所有可能的时间段对中，他希望选择使得两个时间段之间的距离最大的那一对。\n\n两个时间段 #cf_span[(l1, r1)] 和 #cf_span[(l2, r2)] 之间的距离定义为：第一个时间段中的一个点与第二个时间段中的一个点之间的最小可能距离，即最小的 #cf_span[|i - j|]，其中 #cf_span[l1 ≤ i ≤ r1] 且 #cf_span[l2 ≤ j ≤ r2]。特别地，当两个时间段相交时，它们之间的距离为 #cf_span[0]。\n\nAnton 想知道，在最佳情况下，他课程之间的休息时间会持续多久。请帮助 Anton 找到这个数值！\n\n输入的第一行包含一个整数 #cf_span[n] #cf_span[(1 ≤ n ≤ 200 000)] —— Anton 可以参加棋类课程的时间段数量。\n\n接下来的 #cf_span[n] 行，每行包含两个整数 #cf_span[l1, i] 和 #cf_span[r1, i] #cf_span[(1 ≤ l1, i ≤ r1, i ≤ 10^9)] —— 第 #cf_span[i] 个棋类课程时间段。\n\n接下来的一行包含一个整数 #cf_span[m] #cf_span[(1 ≤ m ≤ 200 000)] —— Anton 可以参加编程课程的时间段数量。\n\n接下来的 #cf_span[m] 行，每行包含两个整数 #cf_span[l2, i] 和 #cf_span[r2, i] #cf_span[(1 ≤ l2, i ≤ r2, i ≤ 10^9)] —— 第 #cf_span[i] 个编程课程时间段。\n\n请输出一个整数 —— 时间段之间可能的最大距离。\n\n在第一个样例中，Anton 可以在时间段 #cf_span[(2, 3)] 参加棋类课程，在时间段 #cf_span[(6, 8)] 参加编程课程。不难看出，此时两个时间段之间的距离为 #cf_span[3]。\n\n在第二个样例中，无论他选择哪一对时间段，它们都会相交。因此答案为 #cf_span[0]。"},{"iden":"input","content":"输入的第一行包含一个整数 #cf_span[n] #cf_span[(1 ≤ n ≤ 200 000)] —— Anton 可以参加棋类课程的时间段数量。接下来的 #cf_span[n] 行，每行包含两个整数 #cf_span[l1, i] 和 #cf_span[r1, i] #cf_span[(1 ≤ l1, i ≤ r1, i ≤ 10^9)] —— 第 #cf_span[i] 个棋类课程时间段。接下来的一行包含一个整数 #cf_span[m] #cf_span[(1 ≤ m ≤ 200 000)] —— Anton 可以参加编程课程的时间段数量。接下来的 #cf_span[m] 行，每行包含两个整数 #cf_span[l2, i] 和 #cf_span[r2, i] #cf_span[(1 ≤ l2, i ≤ r2, i ≤ 10^9)] —— 第 #cf_span[i] 个编程课程时间段。"},{"iden":"output","content":"请输出一个整数 —— 时间段之间可能的最大距离。"},{"iden":"examples","content":"输入\n3\n1 5\n2 6\n2 3\n2\n2 4\n6 8\n输出\n3\n\n输入\n3\n1 5\n2 6\n3 7\n2\n2 4\n1 4\n输出\n0"},{"iden":"note","content":"在第一个样例中，Anton 可以在时间段 #cf_span[(2, 3)] 参加棋类课程，在时间段 #cf_span[(6, 8)] 参加编程课程。不难看出，此时两个时间段之间的距离为 #cf_span[3]。\n\n在第二个样例中，无论他选择哪一对时间段，它们都会相交。因此答案为 #cf_span[0]。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ C = \\{(l_{1,i}, r_{1,i}) \\mid i \\in \\{1, \\dots, n\\} \\} $ be the set of chess class time intervals.  \nLet $ P = \\{(l_{2,j}, r_{2,j}) \\mid j \\in \\{1, \\dots, m\\} \\} $ be the set of programming class time intervals.  \n\n**Distance Function**  \nFor two intervals $ I_1 = [l_1, r_1] $, $ I_2 = [l_2, r_2] $, define the distance:  \n$$\nd(I_1, I_2) = \n\\begin{cases}\n0 & \\text{if } [l_1, r_1] \\cap [l_2, r_2] \\neq \\emptyset \\\\\n\\min(|r_1 - l_2|, |r_2 - l_1|) & \\text{otherwise}\n\\end{cases}\n$$\n\n**Objective**  \nCompute:  \n$$\n\\max_{(I_1, I_2) \\in C \\times P} d(I_1, I_2)\n$$","simple_statement":null,"has_page_source":false}