{"raw_statement":[{"iden":"statement","content":"Butler Ostin wants to show Arkady that rows of odd number of fountains are beautiful, while rows of even number of fountains are not.\n\nThe butler wants to show Arkady _n_ gardens. Each garden is a row of _m_ cells, the _i_\\-th garden has one fountain in each of the cells between _l__i_ and _r__i_ inclusive, and there are no more fountains in that garden. The issue is that some of the gardens contain even number of fountains, it is wrong to show them to Arkady.\n\nOstin wants to choose two integers _a_ ≤ _b_ and show only part of each of the gardens that starts at cell _a_ and ends at cell _b_. Of course, only such segments suit Ostin that each garden has either zero or odd number of fountains on this segment. Also, it is necessary that at least one garden has at least one fountain on the segment from _a_ to _b_.\n\nHelp Ostin to find the total length of all such segments, i.e. sum up the value (_b_ - _a_ + 1) for each suitable pair (_a_, _b_)."},{"iden":"input","content":"The first line contains two integers _n_ and _m_ (1 ≤ _n_, _m_ ≤ 2·105) — the number of gardens and the length of each garden.\n\n_n_ lines follow. The _i_\\-th of these lines contains two integers _l__i_ and _r__i_ (1 ≤ _l__i_ ≤ _r__i_ ≤ _m_) — the bounds of the segment that contains fountains in the _i_\\-th garden."},{"iden":"output","content":"Print one integer: the total length of all suitable segments."},{"iden":"examples","content":"Input\n\n1 5\n2 4\n\nOutput\n\n23\n\nInput\n\n3 6\n2 4\n3 6\n4 4\n\nOutput\n\n19"},{"iden":"note","content":"In the first example the following pairs suit Ostin: (_a_, _b_): (1, 2), (1, 4), (1, 5), (2, 2), (2, 4), (2, 5), (3, 3), (4, 4), (4, 5).\n\nIn the second example the following pairs suit Ostin: (_a_, _b_): (1, 2), (1, 5), (2, 2), (2, 5), (3, 3), (4, 4), (4, 6), (5, 5), (6, 6)."}],"translated_statement":[{"iden":"statement","content":"园丁 Ostin 想向 Arkady 展示：包含奇数个喷泉的行是美丽的，而包含偶数个喷泉的行则不是。\n\n园丁想向 Arkady 展示 #cf_span[n] 个花园。每个花园是一行包含 #cf_span[m] 个格子的序列，第 #cf_span[i] 个花园在区间 #cf_span[li] 到 #cf_span[ri]（含）的每个格子中各有一个喷泉，除此之外没有其他喷泉。问题是，有些花园包含偶数个喷泉，不适合展示给 Arkady。\n\nOstin 希望选择两个整数 #cf_span[a ≤ b]，仅展示每个花园中从第 #cf_span[a] 个格子到第 #cf_span[b] 个格子的部分。当然，只有满足以下条件的区间才符合 Ostin 的要求：每个花园在该区间内要么有零个喷泉，要么有奇数个喷泉。此外，至少有一个花园在区间 #cf_span[a] 到 #cf_span[b] 内至少有一个喷泉。\n\n请帮助 Ostin 计算所有满足条件的区间的总长度，即对每个合法的区间对 #cf_span[(a, b)]，求和 #cf_span[(b - a + 1)]。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 2·105]）——花园的数量和每个花园的长度。\n\n接下来 #cf_span[n] 行，第 #cf_span[i] 行包含两个整数 #cf_span[li] 和 #cf_span[ri]（#cf_span[1 ≤ li ≤ ri ≤ m]）——第 #cf_span[i] 个花园中喷泉所在的区间边界。\n\n输出一个整数：所有满足条件的区间的总长度。\n\n在第一个示例中，以下区间对符合 Ostin 的要求：#cf_span[(a, b)]：#cf_span[(1, 2)]、#cf_span[(1, 4)]、#cf_span[(1, 5)]、#cf_span[(2, 2)]、#cf_span[(2, 4)]、#cf_span[(2, 5)]、#cf_span[(3, 3)]、#cf_span[(4, 4)]、#cf_span[(4, 5)]。\n\n在第二个示例中，以下区间对符合 Ostin 的要求：#cf_span[(a, b)]：#cf_span[(1, 2)]、#cf_span[(1, 5)]、#cf_span[(2, 2)]、#cf_span[(2, 5)]、#cf_span[(3, 3)]、#cf_span[(4, 4)]、#cf_span[(4, 6)]、#cf_span[(5, 5)]、#cf_span[(6, 6)]。"},{"iden":"input","content":"第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 2·105]）——花园的数量和每个花园的长度。#cf_span[n] 行后续，第 #cf_span[i] 行包含两个整数 #cf_span[li] 和 #cf_span[ri]（#cf_span[1 ≤ li ≤ ri ≤ m]）——第 #cf_span[i] 个花园中喷泉所在的区间边界。"},{"iden":"output","content":"输出一个整数：所有满足条件的区间的总长度。"},{"iden":"examples","content":"输入1 52 4输出23输入3 62 43 64 4输出19"},{"iden":"note","content":"在第一个示例中，以下区间对符合 Ostin 的要求：#cf_span[(a, b)]：#cf_span[(1, 2)]、#cf_span[(1, 4)]、#cf_span[(1, 5)]、#cf_span[(2, 2)]、#cf_span[(2, 4)]、#cf_span[(2, 5)]、#cf_span[(3, 3)]、#cf_span[(4, 4)]、#cf_span[(4, 5)]。在第二个示例中，以下区间对符合 Ostin 的要求：#cf_span[(a, b)]：#cf_span[(1, 2)]、#cf_span[(1, 5)]、#cf_span[(2, 2)]、#cf_span[(2, 5)]、#cf_span[(3, 3)]、#cf_span[(4, 4)]、#cf_span[(4, 6)]、#cf_span[(5, 5)]、#cf_span[(6, 6)]。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ be the number of gardens and the length of each garden, respectively.  \nLet $ G = \\{([l_i, r_i]) \\mid i \\in \\{1, \\dots, n\\}\\} $ be the set of fountain intervals, where $ 1 \\le l_i \\le r_i \\le m $.  \n\nLet $ \\mathcal{S} = \\{(a, b) \\in \\mathbb{Z}^2 \\mid 1 \\le a \\le b \\le m\\} $ be the set of all possible segments.  \n\nFor a segment $ (a, b) $, define the **fountain count** in garden $ i $ as:  \n$$\nc_i(a,b) = |[l_i, r_i] \\cap [a, b]| = \\max(0, \\min(r_i, b) - \\max(l_i, a) + 1)\n$$  \n\n**Constraints**  \nA segment $ (a, b) \\in \\mathcal{S} $ is **valid** if:  \n1. For all $ i \\in \\{1, \\dots, n\\} $, $ c_i(a,b) = 0 $ or $ c_i(a,b) $ is odd.  \n2. There exists at least one $ i \\in \\{1, \\dots, n\\} $ such that $ c_i(a,b) \\ge 1 $.  \n\n**Objective**  \nCompute:  \n$$\n\\sum_{\\substack{(a,b) \\in \\mathcal{S} \\\\ (a,b) \\text{ valid}}} (b - a + 1)\n$$","simple_statement":null,"has_page_source":false}