{"raw_statement":[{"iden":"statement","content":"Марина любит нечётные значения. Однажды она выписала на доске все от $A$ до $B$ включительно, а затем стерла те числа, сумма цифр которых чётна. Определите, сколько чисел осталось на доске.\n\nПрограмма получает на вход два натуральных числа $A$ и $B$, $A <=.slant B$.\n\nПрограмма должна вывести единственное число — количество чисел с нечётной суммой цифр из выписанных на доске.\n\nРешение правильно работающее для случая, когда числа $A$ и $B$ однозначные, будет оцениваться в 20 баллов.\n\nРешение, правильно работающее для случая, когда числа $A$ и $B$ не превосходят 100, будет оцениваться в 40 баллов.\n\nРешение, правильно работающее для случая, когда числа $A$ и $B$ не превосходят 10000, будет оцениваться в 60 баллов.\n\nВ 100 баллов оценивается решение, которое работает для случаев когда числа $A$ и $B$ не превосходят $10^9$.\n\n"},{"iden":"входные данные","content":"Программа получает на вход два натуральных числа $A$ и $B$, $A <=.slant B$."},{"iden":"выходные данные","content":"Программа должна вывести единственное число — количество чисел с нечётной суммой цифр из выписанных на доске."},{"iden":"система оценки","content":"Решение правильно работающее для случая, когда числа $A$ и $B$ однозначные, будет оцениваться в 20 баллов.Решение, правильно работающее для случая, когда числа $A$ и $B$ не превосходят 100, будет оцениваться в 40 баллов.Решение, правильно работающее для случая, когда числа $A$ и $B$ не превосходят 10000, будет оцениваться в 60 баллов.В 100 баллов оценивается решение, которое работает для случаев когда числа $A$ и $B$ не превосходят $10^9$."},{"iden":"примеры","content":"Входные данные10\n20\nВыходные данные5\nВходные данные20\n20\nВыходные данные0\n"}],"translated_statement":[{"iden":"statement","content":"在一个王国中有 N 个人。第 i 个人居住在点 #cf_span[(xi, yi)]。你是一个怪物，需要在王国中游走并捕获所有 N 个人。\n\n你的旅程如下：\n\n你需要处理 Q 个查询，分为两种类型：\n\n在本题中，你将获得一个整数 BASE 和多个查询。你需要初始化 #cf_span[T = 0]。\n\n类型 0 的查询表示指定的人移动到点 #cf_span[((a1 * T + b1)%BASE, (a2 * T + b2)%BASE)]。\n\n对于类型 1 的查询，你需要输出从点 #cf_span[((a1 * T + b1)%BASE, (a2 * T + b2)%BASE)] 出发捕获所有人所需的最短时间。你应将 #cf_span[T] 的值更新为计算出的时间。\n\n输入的第一行包含三个整数 #cf_span[N], #cf_span[Q] 和 #cf_span[BASE]（#cf_span[0 ≤ N, Q ≤ 10^5], #cf_span[0 ≤ BASE ≤ 10^9]）。接下来的 N 行每行包含两个整数 #cf_span[xi] 和 #cf_span[yi]（#cf_span[0 ≤ xi, yi ≤ BASE]），表示每个人的坐标。\n\n接下来的 #cf_span[Q] 行包含以下类型的查询：\n\n对于每个类型 1 的查询，输出一个整数——完成捕获所有人旅程所需的最短时间，每个答案占一行。"},{"iden":"input","content":"输入的第一行包含三个整数 #cf_span[N], #cf_span[Q] 和 #cf_span[BASE]（#cf_span[0 ≤ N, Q ≤ 10^5], #cf_span[0 ≤ BASE ≤ 10^9]）。接下来的 N 行每行包含两个整数 #cf_span[xi] 和 #cf_span[yi]（#cf_span[0 ≤ xi, yi ≤ BASE]），表示每个人的坐标。接下来的 #cf_span[Q] 行包含以下类型的查询：\n\n#cf_span[0] #cf_span[i] #cf_span[a1] #cf_span[b1] #cf_span[a2] #cf_span[b2]\n#cf_span[1] #cf_span[a1] #cf_span[b1] #cf_span[a2] #cf_span[b2]\n\n其中 #cf_span[i] 是人的编号（#cf_span[1 ≤ i ≤ N]），#cf_span[a1], #cf_span[b1], #cf_span[a2], #cf_span[b2] 是前述的值（#cf_span[0 ≤ a1, b1, a2, b2 ≤ 10^9]）。"},{"iden":"output","content":"对于每个类型 1 的查询，输出一个整数——完成捕获所有人旅程所需的最短时间，每个答案占一行。"},{"iden":"examples","content":"输入\n3 4 1000000000\n2 2\n3 1\n7 0\n1 2 4 3 5\n0 3 1 1 7 3\n1 4 3 2 6\n0 2 2 7 4 1\n输出\n28\n728"},{"iden":"note","content":"在样例测试用例中，你处理了四个查询：\n\n你计算从 (4, 5) 出发的旅程的最短时间，答案为 28。你输出该答案并将 T 更新为 28；\n第 3 个人移动到 (29, 199)；\n你计算从 (115, 62) 出发的旅程的最短时间，答案为 728。你输出该答案并将 T 更新为 728；\n第 2 个人移动到 (1463, 2913)。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N, Q, \\text{BASE} \\in \\mathbb{Z}_{\\geq 0} $ with $ N, Q \\leq 10^5 $, $ \\text{BASE} \\leq 10^9 $.  \nLet $ P = \\{(x_i, y_i) \\mid i \\in \\{1, \\dots, N\\}\\} \\subseteq [0, \\text{BASE})^2 $ be the initial set of person positions.  \nLet $ T \\in \\mathbb{Z}_{\\geq 0} $ be a global state variable, initialized to $ 0 $.  \nLet $ a_1, a_2, b_1, b_2 \\in \\mathbb{Z} $ be fixed parameters (implied by context).  \n\n**Constraints**  \n1. $ 0 \\leq N, Q \\leq 10^5 $  \n2. $ 0 \\leq \\text{BASE} \\leq 10^9 $  \n3. $ 0 \\leq x_i, y_i < \\text{BASE} $ for all $ i \\in \\{1, \\dots, N\\} $  \n4. For each query:  \n   - Type 0: Person moves to $ \\left( (a_1 \\cdot T + b_1) \\bmod \\text{BASE},\\ (a_2 \\cdot T + b_2) \\bmod \\text{BASE} \\right) $  \n   - Type 1: Compute minimum TSP tour length starting from $ \\left( (a_1 \\cdot T + b_1) \\bmod \\text{BASE},\\ (a_2 \\cdot T + b_2) \\bmod \\text{BASE} \\right) $, visiting all $ N $ points, using Manhattan distance: $ d((x_1,y_1), (x_2,y_2)) = |x_1 - x_2| + |y_1 - y_2| $. Update $ T \\leftarrow \\text{result} $.  \n\n**Objective**  \nFor each query of type 1, output:  \n$$\n\\min_{\\sigma \\in S_N} \\left( d\\left(S, P_{\\sigma(1)}\\right) + \\sum_{i=1}^{N-1} d\\left(P_{\\sigma(i)}, P_{\\sigma(i+1)}\\right) \\right)\n$$  \nwhere $ S = \\left( (a_1 \\cdot T + b_1) \\bmod \\text{BASE},\\ (a_2 \\cdot T + b_2) \\bmod \\text{BASE} \\right) $, and $ S_N $ is the set of all permutations of $ \\{1, \\dots, N\\} $.  \nThen update $ T \\leftarrow $ this minimum value.","simple_statement":null,"has_page_source":false}