{"problem":{"name":"D. Tanks","description":{"content":"Petya sometimes has to water his field. To water the field, Petya needs a tank with exactly _V_ ml of water. Petya has got _N_ tanks, _i_\\-th of them initially containing _a__i_ ml of water. The tank","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF920D"},"statements":[{"statement_type":"Markdown","content":"Petya sometimes has to water his field. To water the field, Petya needs a tank with exactly _V_ ml of water.\n\nPetya has got _N_ tanks, _i_\\-th of them initially containing _a__i_ ml of water. The tanks are really large, any of them can contain any amount of water (no matter how large this amount is).\n\nAlso Petya has got a scoop that can contain up to _K_ ml of water (initially the scoop is empty). This scoop can be used to get some water from some tank, and after that pour it all into some tank (it is impossible to get water from multiple tanks without pouring it, or leave some water in the scoop when pouring it). When Petya tries to get some water from a tank, he gets _min_(_v_, _K_) water, where _v_ is the current volume of water in the tank.\n\nIs it possible to obtain a tank with exactly _V_ ml of water using these operations? If it is possible, print a sequence of operations that allows to do it. If there are multiple ways to obtain needed amount of water in some tank, print any of them.\n\n## Input\n\nThe first line contains 3 integers: _N_ (2 ≤ _N_ ≤ 5000), _K_ (1 ≤ _K_ ≤ 5000), and _V_ (0 ≤ _V_ ≤ 109) — the number of tanks, the maximum volume of water the scoop can contain, and the required amount of water in some tank, respectively.\n\nThe second line contains _N_ integers _a__i_ (0 ≤ _a__i_ ≤ 105), where _a__i_ is initial volume of water in _i_\\-th tank.\n\n## Output\n\nIf it is impossible to obtain a tank with exactly _V_ ml of water, print _NO_.\n\nOtherwise print _YES_ in the first line, and beginning from the second line, print the sequence of operations in the following format:\n\nEach line has to contain 3 numbers denoting a compressed operation: \"_cnt_ _x_ _y_\" (1 ≤ _cnt_ ≤ 109, 1 ≤ _x_, _y_ ≤ _N_), where _x_ is the index of the tank where we get water, _y_ is the index of the tank where we pour water, and _cnt_ is the number of times we transfer water from tank _x_ to tank _y_.\n\nThe number of these lines **must not exceed _N_ + 5**.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Petya 有时需要给他的田地浇水。为了给田地浇水，Petya 需要一个恰好含有 #cf_span[V] 毫升水的水箱。\n\nPetya 拥有 #cf_span[N] 个水箱，第 #cf_span[i] 个水箱初始含有 #cf_span[ai] 毫升水。这些水箱非常大，任何一个都可以容纳任意多的水（无论这个量有多大）。\n\n此外，Petya 还有一个勺子，最多可以盛装 #cf_span[K] 毫升水（初始时勺子是空的）。这个勺子可用于从某个水箱中取出一些水，然后将全部水倒入另一个水箱中（不允许在不倾倒的情况下从多个水箱取水，也不允许在倾倒时在勺子中残留水）。当 Petya 尝试从一个水箱取水时，他会获得 #cf_span[min(v, K)] 毫升水，其中 #cf_span[v] 是该水箱当前的水量。\n\n能否通过这些操作获得一个恰好含有 #cf_span[V] 毫升水的水箱？如果可以，请输出一个允许实现该目标的操作序列。如果有多种方式可以在某个水箱中获得所需水量，请输出其中任意一种。\n\n第一行包含 #cf_span[3] 个整数：#cf_span[N] #cf_span[(2 ≤ N ≤ 5000)]、#cf_span[K] #cf_span[(1 ≤ K ≤ 5000)] 和 #cf_span[V] #cf_span[(0 ≤ V ≤ 109)] —— 分别表示水箱数量、勺子的最大容量和所需水箱中的水量。\n\n第二行包含 #cf_span[N] 个整数 #cf_span[ai] #cf_span[(0 ≤ ai ≤ 105)]，其中 #cf_span[ai] 表示第 #cf_span[i] 个水箱的初始水量。\n\n如果无法获得一个恰好含有 #cf_span[V] 毫升水的水箱，请输出 _NO_。\n\n否则，第一行输出 _YES_，随后从第二行开始，按以下格式输出操作序列：\n\n每行包含 #cf_span[3] 个数字，表示一个压缩操作：“#cf_span[cnt] #cf_span[x] #cf_span[y]” #cf_span[(1 ≤ cnt ≤ 109, 1 ≤ x, y ≤ N)]，其中 #cf_span[x] 是从中取水的水箱编号，#cf_span[y] 是向其倒水的水箱编号，#cf_span[cnt] 是从水箱 #cf_span[x] 向水箱 #cf_span[y] 转移水的次数。\n\n这些行的数量 *不得超过 #cf_span[N + 5]*。\n\n## Input\n\n第一行包含 #cf_span[3] 个整数：#cf_span[N] #cf_span[(2 ≤ N ≤ 5000)]、#cf_span[K] #cf_span[(1 ≤ K ≤ 5000)] 和 #cf_span[V] #cf_span[(0 ≤ V ≤ 109)] —— 分别表示水箱数量、勺子的最大容量和所需水箱中的水量。第二行包含 #cf_span[N] 个整数 #cf_span[ai] #cf_span[(0 ≤ ai ≤ 105)]，其中 #cf_span[ai] 表示第 #cf_span[i] 个水箱的初始水量。\n\n## Output\n\n如果无法获得一个恰好含有 #cf_span[V] 毫升水的水箱，请输出 _NO_。否则，第一行输出 _YES_，随后从第二行开始，按以下格式输出操作序列：每行包含 #cf_span[3] 个数字，表示一个压缩操作：“#cf_span[cnt] #cf_span[x] #cf_span[y]” #cf_span[(1 ≤ cnt ≤ 109, 1 ≤ x, y ≤ N)]，其中 #cf_span[x] 是从中取水的水箱编号，#cf_span[y] 是向其倒水的水箱编号，#cf_span[cnt] 是从水箱 #cf_span[x] 向水箱 #cf_span[y] 转移水的次数。这些行的数量 *不得超过 #cf_span[N + 5]*。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N, K, V \\in \\mathbb{Z} $ be given integers:  \n- $ N $: number of tanks, $ 2 \\leq N \\leq 5000 $  \n- $ K $: maximum scoop capacity, $ 1 \\leq K \\leq 5000 $  \n- $ V $: target volume, $ 0 \\leq V \\leq 10^9 $  \n\nLet $ A = (a_1, a_2, \\dots, a_N) \\in \\mathbb{Z}_{\\geq 0}^N $ be the initial water volumes in the tanks.  \n\nA *transfer operation* is defined as moving $ \\min(v, K) $ water from tank $ x $ to tank $ y $, where $ v $ is the current volume in tank $ x $. A *compressed operation* $ (\\text{cnt}, x, y) $ represents repeating this transfer $ \\text{cnt} $ times.  \n\n**Constraints**  \n1. Each transfer from tank $ x $ to tank $ y $ removes $ \\min(v_x, K) $ from $ x $ and adds it to $ y $, where $ v_x $ is the volume in $ x $ *before* the transfer.  \n2. The sequence of compressed operations must consist of at most $ N + 5 $ lines.  \n3. Each $ \\text{cnt} \\in \\mathbb{Z} $, $ 1 \\leq \\text{cnt} \\leq 10^9 $.  \n4. Tank indices $ x, y \\in \\{1, \\dots, N\\} $.  \n\n**Objective**  \nDetermine if there exists a sequence of compressed operations such that after execution, at least one tank contains exactly $ V $ ml of water.  \n- If possible: output \"YES\" followed by such a sequence.  \n- If impossible: output \"NO\".","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF920D","tags":["dp","greedy","implementation"],"sample_group":[["2 3 5\n2 3","YES\n1 2 1"],["2 3 4\n2 3","NO"],["5 2 0\n1 3 5 7 9","YES\n2 2 1\n3 3 1\n4 4 1\n5 5 1"]],"created_at":"2026-03-03 11:00:39"}}