{"problem":{"name":"F. Passports","description":{"content":"Gleb is a famous competitive programming teacher from Innopolis. He is planning a trip to _N_ programming camps in the nearest future. Each camp will be held in a different country. For each of them, ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF1012F"},"statements":[{"statement_type":"Markdown","content":"Gleb is a famous competitive programming teacher from Innopolis. He is planning a trip to _N_ programming camps in the nearest future. Each camp will be held in a different country. For each of them, Gleb needs to apply for a visa.\n\nFor each of these trips Gleb knows three integers: the number of the first day of the trip _s__i_, the length of the trip in days _len__i_, and the number of days _t__i_ this country's consulate will take to process a visa application and stick a visa in a passport. Gleb has _P_ (1 ≤ _P_ ≤ 2) valid passports and is able to decide which visa he wants to put in which passport.\n\nFor each trip, Gleb will have a flight to that country early in the morning of the day _s__i_ and will return back late in the evening of the day _s__i_ + _len__i_ - 1.\n\nTo apply for a visa on the day _d_, Gleb needs to be in Innopolis in the middle of this day. So he can't apply for a visa while he is on a trip, including the first and the last days. If a trip starts the next day after the end of the other one, Gleb can't apply for a visa between them as well. The earliest Gleb can apply for a visa is day 1.\n\nAfter applying for a visa of country _i_ on day _d_, Gleb will get his passport back in the middle of the day _d_ + _t__i_. Consulates use delivery services, so Gleb can get his passport back even if he is not in Innopolis on this day. Gleb can apply for another visa on the same day he received his passport back, if he is in Innopolis this day.\n\nGleb will not be able to start his trip on day _s__i_ if he doesn't has a passport with a visa for the corresponding country in the morning of day _s__i_. In particular, the passport should not be in another country's consulate for visa processing.\n\nHelp Gleb to decide which visas he needs to receive in which passport, and when he should apply for each visa.\n\n## Input\n\nIn the first line of the input there are two integers _N_ (1 ≤ _N_ ≤ 22) and _P_ (1 ≤ _P_ ≤ 2)—the number of trips and the number of passports Gleb has, respectively.\n\nThe next _N_ lines describe Gleb's trips. Each line contains three positive integers _s__i_, _len__i_, _t__i_ (1 ≤ _s__i_, _len__i_, _t__i_ ≤ 109)—the first day of the trip, the length of the trip and number of days the consulate of this country needs to process a visa application. It is guaranteed that no two trips intersect.\n\n## Output\n\nIf it is impossible to get all visas on time, just print \"NO\" (quotes for clarity). Otherwise, print \"YES\" and _N_ lines describing trips. For each trip, first print number of the passport Gleb should put this country's visa in, and then print number of the day he should apply for it. Print trips in the same order as they appear in the input. Days are numbered from 1, starting with tomorrow—the first day you can apply for a visa. Passports are numbered from 1 to _P_.\n\nIf there are several possible answers, print any of them.\n\n[samples]\n\n## Note\n\nExamples with answer \"YES\" are depicted below.\n\nEach cell of the stripe represents a single day. Rectangles represent trips, each trip starts in the morning and ends in the evening. Rectangles with angled corners represent visa applications. Each application starts in the middle of a day and ends _t__i_ days after. The trip and the visa application for the same country have the same color.\n\nIn examples with two passports, visa applications and trips depicted above the time stripe are made using the first passport, visa applications and trips depicted below the time stripe are made using the second passport.\n\n**Example 1**:\n\n**Example 2**:\n\n**Example 3**:\n\n","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"[{\"iden\":\"statement\",\"content\":\"Gleb 是来自 Innopolis 的著名竞赛编程教练。他计划在未来前往 #cf_span[N] 个编程训练营。每个训练营将在不同的国家举行，因此他需要为每个国家申请签证。\\n\\n对于每次旅行，Gleb 知道三个整数：旅行的第一天 #cf_span[si]、旅行的持续天数 #cf_span[leni]，以及该国领事馆处理签证申请并贴签证到护照所需的天数 #cf_span[ti]。Gleb 拥有 #cf_span[P]（#cf_span[1 ≤ P ≤ 2]）本有效的护照，并可以决定将哪个签证放入哪个护照。\\n\\n对于每次旅行，Gleb 将在 day #cf_span[si] 清晨乘飞机前往该国，并在 day #cf_span[si + leni - 1] 晚上返回。\\n\\n要在 day #cf_span[d] 申请签证，Gleb 必须在当天中午时分位于 Innopolis。因此，他在旅行期间（包括第一天和最后一天）无法申请签证。如果一次旅行紧接在另一次旅行之后开始（即前一次旅行的最后一天与下一次旅行的第一天是连续的），那么他也不能在两次旅行之间申请签证。Gleb 最早可以在 day 1 申请签证。\\n\\n如果 Gleb 在 day #cf_span[d] 申请了国家 #cf_span[i] 的签证，他将在 day #cf_span[d + ti] 中午收到护照。领事馆使用快递服务，因此即使 Gleb 当天不在 Innopolis，他也能收到护照。如果他在收到护照的当天位于 Innopolis，他可以在同一天再次申请另一张签证。\\n\\n如果在 day #cf_span[si] 清晨，Gleb 没有携带对应国家签证的护照，他将无法开始该次旅行。特别是，护照不能正处于另一国领事馆的签证处理过程中。\\n\\n请帮助 Gleb 决定每张签证应放入哪个护照，以及何时申请每张签证。\\n\\n输入的第一行包含两个整数 #cf_span[N]（#cf_span[1 ≤ N ≤ 22]）和 #cf_span[P]（#cf_span[1 ≤ P ≤ 2]），分别表示旅行次数和 Gleb 拥有的护照数量。\\n\\n接下来的 #cf_span[N] 行描述了 Gleb 的每次旅行。每行包含三个正整数 #cf_span[si]、#cf_span[leni]、#cf_span[ti]（#cf_span[1 ≤ si, leni, ti ≤ 10^9]），分别表示旅行的第一天、旅行持续天数和领事馆处理签证所需的天数。保证任意两次旅行不重叠。\\n\\n如果无法按时获得所有签证，请仅输出 \\\"NO\\\"（不含引号）。否则，输出 \\\"YES\\\"，并输出 #cf_span[N] 行，每行描述一次旅行：首先输出 Gleb 应将该国签证放入的护照编号，然后输出他应申请签证的日期。输出顺序需与输入中旅行的顺序一致。日期从 1 开始编号，1 表示明天（最早可申请签证的日期）。护照编号从 1 到 #cf_span[P]。\\n\\n如果有多个可行答案，输出任意一个即可。\\n\\n以下为若干 \\\"YES\\\" 答案的示例。\\n\\n每条横线中的一个格子代表一天。矩形代表旅行，每个旅行从清晨开始，到傍晚结束。带斜角的矩形代表签证申请，每个申请从某天中午开始，持续 #cf_span[ti] 天后结束。同一国家的旅行与签证申请使用相同颜色。\\n\\n在有两个护照的示例中，位于时间横线上方的签证申请和旅行使用第一个护照，位于下方的使用第二个护照。\\n\\n*示例 1*： \\n\\n*示例 2*： \\n\\n*示例 3*： \\n\\n\"},{\"iden\":\"input\",\"content\":\"在输入的第一行有两个整数 #cf_span[N]（#cf_span[1 ≤ N ≤ 22]）和 #cf_span[P]（#cf_span[1 ≤ P ≤ 2]），分别表示旅行次数和 Gleb 拥有的护照数量。接下来的 #cf_span[N] 行描述了 Gleb 的旅行。每行包含三个正整数 #cf_span[si]、#cf_span[leni]、#cf_span[ti]（#cf_span[1 ≤ si, leni, ti ≤ 10^9]），分别表示旅行的第一天、旅行持续天数和该国领事馆处理签证所需的天数。保证任意两次旅行不重叠。\"},{\"iden\":\"output\",\"content\":\"如果无法按时获得所有签证，请仅输出 \\\"NO\\\"（不含引号）。否则，输出 \\\"YES\\\"，并输出 #cf_span[N] 行，每行描述一次旅行：首先输出 Gleb 应将该国签证放入的护照编号，然后输出他应申请签证的日期。输出顺序需与输入中旅行的顺序一致。日期从 1 开始编号，1 表示明天（最早可申请签证的日期）。护照编号从 1 到 #cf_span[P]。如果有多个可行答案，输出任意一个即可。\"},{\"iden\":\"examples\",\"content\":\"输入：\\n2 1\\n3 1 1\\n6 1 1\\n输出：\\nYES\\n1 1\\n1 4\\n\\n输入：\\n3 1\\n13 2 2\\n7 3 1\\n19 3 4\\n输出：\\nYES\\n1 10\\n1 1\\n1 2\\n\\n输入：\\n7 2\\n15 1 1\\n14 1 1\\n18 1 1\\n21 1 1\\n9 4 6\\n22 2 5\\n5 4 3\\n输出：\\nYES\\n2 13\\n1 1\\n1 16\\n1 19\\n2 2\\n1 16\\n2 1\\n\\n输入：\\n3 1\\n7 3 1\\n13 2 3\\n19 3 4\\n输出：\\nNO\"},{\"iden\":\"note\",\"content\":\"以下为若干 \\\"YES\\\" 答案的示例。每条横线中的一个格子代表一天。矩形代表旅行，每个旅行从清晨开始，到傍晚结束。带斜角的矩形代表签证申请，每个申请从某天中午开始，持续 #cf_span[ti] 天后结束。同一国家的旅行与签证申请使用相同颜色。在有两个护照的示例中，位于时间横线上方的签证申请和旅行使用第一个护照，位于下方的使用第二个护照。\\n\\n*示例 1*： \\n*示例 2*： \\n*示例 3*： \"}]}","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions** \nLet $ N \\in \\mathbb{Z}^+ $ be the number of trips, $ P \\in \\{1, 2\\} $ the number of passports. \nFor each trip $ i \\in \\{1, \\dots, N\\} $: \n- $ s_i \\in \\mathbb{Z}^+ $: first day of trip (morning). \n- $ \\text{len}_i \\in \\mathbb{Z}^+ $: duration of trip in days. \n- $ t_i \\in \\mathbb{Z}^+ $: visa processing time in days. \nThe trip occupies days $ [s_i, s_i + \\text{len}_i - 1] $ (inclusive, both endpoints). \n\nLet $ A_i \\in \\mathbb{Z}^+ $ be the day on which Gleb applies for visa $ i $. \nLet $ p_i \\in \\{1, \\dots, P\\} $ be the passport assigned to visa $ i $. \n\n**Constraints** \n1. **Trip confinement**: Gleb cannot apply for any visa during a trip: \n $$\n A_i \\notin \\bigcup_{j=1}^N [s_j, s_j + \\text{len}_j - 1] \\quad \\forall i \\in \\{1, \\dots, N\\}\n $$\n\n2. **Visa completion**: Visa $ i $ must be ready by the morning of day $ s_i $: \n $$\n A_i + t_i \\leq s_i\n $$\n\n3. **Passport uniqueness per trip**: Each visa is assigned to exactly one passport. \n No two visa applications using the same passport may overlap in processing: \n $$\n \\forall i \\ne j \\text{ with } p_i = p_j: \\quad [A_i, A_i + t_i - 1] \\cap [A_j, A_j + t_j - 1] = \\emptyset\n $$\n\n4. **Earliest application**: \n $$\n A_i \\geq 1 \\quad \\forall i \\in \\{1, \\dots, N\\}\n $$\n\n**Objective** \nDetermine assignments $ (p_i, A_i) $ for all $ i \\in \\{1, \\dots, N\\} $ satisfying all constraints above. \nIf no such assignment exists, output \"NO\". Otherwise, output \"YES\" followed by $ N $ lines, each containing $ p_i $ and $ A_i $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF1012F","tags":["dp","implementation"],"sample_group":[["2 1\n3 1 1\n6 1 1","YES\n1 1\n1 4"],["3 1\n13 2 2\n7 3 1\n19 3 4","YES\n1 10\n1 1\n1 2"],["7 2\n15 1 1\n14 1 1\n18 1 1\n21 1 1\n9 4 6\n22 2 5\n5 4 3","YES\n2 13\n1 1\n1 16\n1 19\n1 2\n2 16\n2 1"],["3 1\n7 3 1\n13 2 3\n19 3 4","NO"]],"created_at":"2026-03-03 11:00:39"}}