huyen89/code_contest_problems
030
1problems2"Andi and Budi were given an assignment to tidy up their bookshelf of n books. Each book is represented by the book title — a string s_i numbered from 1 to n, each with length m. Andi really wants to sort the book lexicographically ascending, while Budi wants to sort it lexicographically descending.3 4Settling their fight, they decided to combine their idea and sort it asc-desc-endingly, where the odd-indexed characters will be compared ascendingly, and the even-indexed characters will be compared descendingly.5 6A string a occurs before a string b in asc-desc-ending order if and only if in the first position where a and b differ, the following holds:7 8 * if it is an odd position, the string a has a letter that appears earlier in the alphabet than the corresponding letter in b; 9 * if it is an even position, the string a has a letter that appears later in the alphabet than the corresponding letter in b. 10 11Input12 13The first line contains two integers n and m (1 ≤ n ⋅ m ≤ 10^6).14 15The i-th of the next n lines contains a string s_i consisting of m uppercase Latin letters — the book title. The strings are pairwise distinct.16 17Output18 19Output n integers — the indices of the strings after they are sorted asc-desc-endingly.20 21Example22 23Input24 25 265 227AA28AB29BB30BA31AZ32 33 34Output35 36 375 2 1 3 438 39Note40 41The following illustrates the first example.42 43<image>"44"Mr. Chanek lives in a city represented as a plane. He wants to build an amusement park in the shape of a circle of radius r. The circle must touch the origin (point (0, 0)).45 46There are n bird habitats that can be a photo spot for the tourists in the park. The i-th bird habitat is at point p_i = (x_i, y_i). 47 48Find the minimum radius r of a park with at least k bird habitats inside. 49 50A point is considered to be inside the park if and only if the distance between p_i and the center of the park is less than or equal to the radius of the park. Note that the center and the radius of the park do not need to be integers.51 52In this problem, it is guaranteed that the given input always has a solution with r ≤ 2 ⋅ 10^5.53 54Input55 56The first line contains two integers n and k (1 ≤ n ≤ 10^5, 1 ≤ k ≤ n) — the number of bird habitats in the city and the number of bird habitats required to be inside the park.57 58The i-th of the next n lines contains two integers x_i and y_i (0 ≤ |x_i|, |y_i| ≤ 10^5) — the position of the i-th bird habitat.59 60Output61 62Output a single real number r denoting the minimum radius of a park with at least k bird habitats inside. It is guaranteed that the given input always has a solution with r ≤ 2 ⋅ 10^5.63 64Your answer is considered correct if its absolute or relative error does not exceed 10^{-4}.65 66Formally, let your answer be a, and the jury's answer be b. Your answer is accepted if and only if \frac{|a - b|}{max{(1, |b|)}} ≤ 10^{-4}.67 68Examples69 70Input71 72 738 474-3 175-4 4761 5772 2782 -279-2 -480-1 -181-6 082 83 84Output85 86 873.162277658988 89 90Input91 92 931 1940 095 96 97Output98 99 1000.0000000000101 102Note103 104In the first example, Mr. Chanek can put the center of the park at (-3, -1) with radius √{10} ≈ 3.162. It can be proven this is the minimum r.105 106The following illustrates the first example. The blue points represent bird habitats and the red circle represents the amusement park.107 108<image>"109"Denote a cyclic sequence of size n as an array s such that s_n is adjacent to s_1. The segment s[r, l] where l < r is the concatenation of s[r, n] and s[1, l].110 111You are given an array a consisting of n integers. Define b as the cyclic sequence obtained from concatenating m copies of a. Note that b has size n ⋅ m.112 113You are given an integer k where k = 1 or k is a prime number. Find the number of different segments in b where the sum of elements in the segment is divisible by k.114 115Two segments are considered different if the set of indices of the segments are different. For example, when n = 3 and m = 2, the set of indices for segment s[2, 5] is \{2, 3, 4, 5\}, and for segment s[5, 2] is \{5, 6, 1, 2\}. In particular, the segments s[1, 6], s[2,1], …, s[6, 5] are considered as the same segment.116 117Output the answer modulo 10^9 + 7.118 119Input120 121The first line contains three integers n, m, and k (1 ≤ n, m, k ≤ 2 ⋅ 10^5, k = 1 or k is a prime number).122 123The second line contains n integers a_1, a_2, …, a_n (0 ≤ a_i ≤ 2 ⋅ 10^5).124 125Output126 127Output an integer denoting the number of different segments in b where the sum of elements in the segment is divisible by k, modulo 10^9 + 7.128 129Examples130 131Input132 133 1345 1 51351 2 3 4 3136 137 138Output139 140 1414142 143 144Input145 146 1475 1 51481 2 3 4 5149 150 151Output152 153 1545155 156 157Input158 159 1605 4 51611 2 3 4 5162 163 164Output165 166 167125168 169Note170 171In the first example, all valid segments are [1,4], [2, 3], [3, 5], and [4, 2].172 173In the second example, one of the valid segments is [1, 5]."174"Mr. Chanek has an integer represented by a string s. Zero or more digits have been erased and are denoted by the character _. There are also zero or more digits marked by the character X, meaning they're the same digit.175 176Mr. Chanek wants to count the number of possible integer s, where s is divisible by 25. Of course, s must not contain any leading zero. He can replace the character _ with any digit. He can also replace the character X with any digit, but it must be the same for every character X.177 178As a note, a leading zero is any 0 digit that comes before the first nonzero digit in a number string in positional notation. For example, 0025 has two leading zeroes. An exception is the integer zero, (0 has no leading zero, but 0000 has three leading zeroes).179 180Input181 182One line containing the string s (1 ≤ |s| ≤ 8). The string s consists of the characters 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, _, and X.183 184Output185 186Output an integer denoting the number of possible integer s.187 188Examples189 190Input191 192 19325194 195 196Output197 198 1991200 201 202Input203 204 205_00206 207 208Output209 210 2119212 213 214Input215 216 217_XX218 219 220Output221 222 2239224 225 226Input227 228 2290230 231 232Output233 234 2351236 237 238Input239 240 2410_25242 243 244Output245 246 2470248 249Note250 251In the first example, the only possible s is 25.252 253In the second and third example, s ∈ \{100, 200,300,400,500,600,700,800,900\}.254 255In the fifth example, all possible s will have at least one leading zero."256"There is a city park represented as a tree with n attractions as its vertices and n - 1 rails as its edges. The i-th attraction has happiness value a_i.257 258Each rail has a color. It is either black if t_i = 0, or white if t_i = 1. Black trains only operate on a black rail track, and white trains only operate on a white rail track. If you are previously on a black train and want to ride a white train, or you are previously on a white train and want to ride a black train, you need to use 1 ticket.259 260The path of a tour must be a simple path — it must not visit an attraction more than once. You do not need a ticket the first time you board a train. You only have k tickets, meaning you can only switch train types at most k times. In particular, you do not need a ticket to go through a path consisting of one rail color.261 262Define f(u, v) as the sum of happiness values of the attractions in the tour (u, v), which is a simple path that starts at the u-th attraction and ends at the v-th attraction. Find the sum of f(u,v) for all valid tours (u, v) (1 ≤ u ≤ v ≤ n) that does not need more than k tickets, modulo 10^9 + 7.263 264Input265 266The first line contains two integers n and k (2 ≤ n ≤ 2 ⋅ 10^5, 0 ≤ k ≤ n-1) — the number of attractions in the city park and the number of tickets you have.267 268The second line contains n integers a_1, a_2,…, a_n (0 ≤ a_i ≤ 10^9) — the happiness value of each attraction.269 270The i-th of the next n - 1 lines contains three integers u_i, v_i, and t_i (1 ≤ u_i, v_i ≤ n, 0 ≤ t_i ≤ 1) — an edge between vertices u_i and v_i with color t_i. The given edges form a tree.271 272Output273 274Output an integer denoting the total happiness value for all valid tours (u, v) (1 ≤ u ≤ v ≤ n), modulo 10^9 + 7.275 276Examples277 278Input279 280 2815 02821 3 2 6 42831 2 12841 4 02853 2 12862 5 0287 288 289Output290 291 29245293 294 295Input296 297 2983 12991 1 13001 2 13013 2 0302 303 304Output305 306 30710"308"Mr. Chanek opened a letter from his fellow, who is currently studying at Singanesia. Here is what it says.309 310Define an array b (0 ≤ b_i < k) with n integers. While there exists a pair (i, j) such that b_i ≠ b_j, do the following operation:311 312 * Randomly pick a number i satisfying 0 ≤ i < n. Note that each number i has a probability of 1/n to be picked. 313 * Randomly Pick a number j satisfying 0 ≤ j < k. 314 * Change the value of b_i to j. It is possible for b_i to be changed to the same value. 315 316 317 318Denote f(b) as the expected number of operations done to b until all elements of b are equal. 319 320You are given two integers n and k, and an array a (-1 ≤ a_i < k) of n integers. 321 322For every index i with a_i = -1, replace a_i with a random number j satisfying 0 ≤ j < k. Let c be the number of occurrences of -1 in a. There are k^c possibilites of a after the replacement, each with equal probability of being the final array.323 324Find the expected value of f(a) modulo 10^9 + 7. 325 326Formally, let M = 10^9 + 7. It can be shown that the answer can be expressed as an irreducible fraction p/q, where p and q are integers and q not ≡ 0 \pmod{M}. Output the integer equal to p ⋅ q^{-1} mod M. In other words, output such an integer x that 0 ≤ x < M and x ⋅ q ≡ p \pmod{M}.327 328After reading the letter, Mr. Chanek gave the task to you. Solve it for the sake of their friendship!329 330Input331 332The first line contains two integers n and k (2 ≤ n ≤ 10^5, 2 ≤ k ≤ 10^9). 333 334The second line contains n integers a_1, a_2, …, a_n (-1 ≤ a_i < k).335 336Output337 338Output an integer denoting the expected value of f(a) modulo 10^9 + 7.339 340Examples341 342Input343 344 3452 23460 1347 348 349Output350 351 3522353 354 355Input356 357 3582 23590 -1360 361 362Output363 364 3651366 367 368Input369 370 3713 33720 1 1373 374 375Output376 377 37812379 380 381Input382 383 3843 3385-1 -1 -1386 387 388Output389 390 39111392 393 394Input395 396 39710 9398-1 0 -1 1 1 2 2 3 3 3399 400 401Output402 403 404652419213"405"Mr. Chanek has an array a of n integers. The prettiness value of a is denoted as:406 407$$$∑_{i=1}^{n} {∑_{j=1}^{n} {\gcd(a_i, a_j) ⋅ \gcd(i, j)}}$$$408 409where \gcd(x, y) denotes the greatest common divisor (GCD) of integers x and y.410 411In other words, the prettiness value of an array a is the total sum of \gcd(a_i, a_j) ⋅ \gcd(i, j) for all pairs (i, j).412 413Help Mr. Chanek find the prettiness value of a, and output the result modulo 10^9 + 7!414 415Input416 417The first line contains an integer n (2 ≤ n ≤ 10^5).418 419The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^5).420 421Output422 423Output an integer denoting the prettiness value of a modulo 10^9 + 7.424 425Example426 427Input428 429 43054313 6 2 1 4432 433 434Output435 436 43777"438"The Winter holiday will be here soon. Mr. Chanek wants to decorate his house's wall with ornaments. The wall can be represented as a binary string a of length n. His favorite nephew has another binary string b of length m (m ≤ n).439 440Mr. Chanek's nephew loves the non-negative integer k. His nephew wants exactly k occurrences of b as substrings in a. 441 442However, Mr. Chanek does not know the value of k. So, for each k (0 ≤ k ≤ n - m + 1), find the minimum number of elements in a that have to be changed such that there are exactly k occurrences of b in a.443 444A string s occurs exactly k times in t if there are exactly k different pairs (p,q) such that we can obtain s by deleting p characters from the beginning and q characters from the end of t.445 446Input447 448The first line contains two integers n and m (1 ≤ m ≤ n ≤ 500) — size of the binary string a and b respectively.449 450The second line contains a binary string a of length n.451 452The third line contains a binary string b of length m.453 454Output455 456Output n - m + 2 integers — the (k+1)-th integer denotes the minimal number of elements in a that have to be changed so there are exactly k occurrences of b as a substring in a.457 458Example459 460Input461 462 4639 3464100101011465101466 467 468Output469 470 4711 1 0 1 6 -1 -1 -1472 473Note474 475For k = 0, to make the string a have no occurrence of 101, you can do one character change as follows.476 477100101011 → 100100011478 479For k = 1, you can also change a single character.480 481100101011 → 100001011482 483For k = 2, no changes are needed."484"Chanek Jones is back, helping his long-lost relative Indiana Jones, to find a secret treasure in a maze buried below a desert full of illusions.485 486The map of the labyrinth forms a tree with n rooms numbered from 1 to n and n - 1 tunnels connecting them such that it is possible to travel between each pair of rooms through several tunnels.487 488The i-th room (1 ≤ i ≤ n) has a_i illusion rate. To go from the x-th room to the y-th room, there must exist a tunnel between x and y, and it takes max(|a_x + a_y|, |a_x - a_y|) energy. |z| denotes the absolute value of z.489 490To prevent grave robbers, the maze can change the illusion rate of any room in it. Chanek and Indiana would ask q queries.491 492There are two types of queries to be done:493 494 * 1\ u\ c — The illusion rate of the x-th room is changed to c (1 ≤ u ≤ n, 0 ≤ |c| ≤ 10^9). 495 * 2\ u\ v — Chanek and Indiana ask you the minimum sum of energy needed to take the secret treasure at room v if they are initially at room u (1 ≤ u, v ≤ n). 496 497 498 499Help them, so you can get a portion of the treasure!500 501Input502 503The first line contains two integers n and q (2 ≤ n ≤ 10^5, 1 ≤ q ≤ 10^5) — the number of rooms in the maze and the number of queries.504 505The second line contains n integers a_1, a_2, …, a_n (0 ≤ |a_i| ≤ 10^9) — inital illusion rate of each room.506 507The i-th of the next n-1 lines contains two integers s_i and t_i (1 ≤ s_i, t_i ≤ n), meaning there is a tunnel connecting s_i-th room and t_i-th room. The given edges form a tree.508 509The next q lines contain the query as described. The given queries are valid.510 511Output512 513For each type 2 query, output a line containing an integer — the minimum sum of energy needed for Chanek and Indiana to take the secret treasure.514 515Example516 517Input518 519 5206 452110 -9 2 -1 4 -65221 55235 45245 65256 25266 35272 1 25281 1 -35292 1 25302 3 3531 532 533Output534 535 53639537325380539 540Note541 542<image>543 544In the first query, their movement from the 1-st to the 2-nd room is as follows.545 546 * 1 → 5 — takes max(|10 + 4|, |10 - 4|) = 14 energy. 547 * 5 → 6 — takes max(|4 + (-6)|, |4 - (-6)|) = 10 energy. 548 * 6 → 2 — takes max(|-6 + (-9)|, |-6 - (-9)|) = 15 energy. 549 550In total, it takes 39 energy.551 552In the second query, the illusion rate of the 1-st room changes from 10 to -3.553 554In the third query, their movement from the 1-st to the 2-nd room is as follows.555 556 * 1 → 5 — takes max(|-3 + 4|, |-3 - 4|) = 7 energy. 557 * 5 → 6 — takes max(|4 + (-6)|, |4 - (-6)|) = 10 energy. 558 * 6 → 2 — takes max(|-6 + (-9)|, |-6 - (-9)|) = 15 energy. 559 560 561 562Now, it takes 32 energy."563"Mr. Chanek has a new game called Dropping Balls. Initially, Mr. Chanek has a grid a of size n × m564 565Each cell (x,y) contains an integer a_{x,y} denoting the direction of how the ball will move.566 567 * a_{x,y}=1 — the ball will move to the right (the next cell is (x, y + 1)); 568 * a_{x,y}=2 — the ball will move to the bottom (the next cell is (x + 1, y)); 569 * a_{x,y}=3 — the ball will move to the left (the next cell is (x, y - 1)). 570 571 572 573Every time a ball leaves a cell (x,y), the integer a_{x,y} will change to 2. Mr. Chanek will drop k balls sequentially, each starting from the first row, and on the c_1, c_2, ..., c_k-th (1 ≤ c_i ≤ m) columns.574 575Determine in which column each ball will end up in (position of the ball after leaving the grid).576 577Input578 579The first line contains three integers n, m, and k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 10^5) — the size of the grid and the number of balls dropped by Mr. Chanek.580 581The i-th of the next n lines contains m integers a_{i,1},a_{i,2},…,a_{i,m} (1 ≤ a_{i,j} ≤ 3). It will satisfy a_{i, 1} ≠ 3 and a_{i, m} ≠ 1.582 583The next line contains k integers c_1, c_2, …, c_k (1 ≤ c_i ≤ m) — the balls' column positions dropped by Mr. Chanek sequentially.584 585Output586 587Output k integers — the i-th integer denoting the column where the i-th ball will end.588 589Examples590 591Input592 593 5945 5 35951 2 3 3 35962 2 2 2 25972 2 2 2 25982 2 2 2 25992 2 2 2 26001 2 1601 602 603Output604 605 6062 2 1 607 608 609Input610 611 6121 2 26131 36141 2615 616 617Output618 619 6201 2 621 622Note623 624In the first example, the first ball will drop as follows. Note that the cell (1, 1) will change direction to the bottom direction.625 626<image>627 628The second and third balls will drop as follows. 629 630<image>631 632All balls will be dropped from the first row and on the c_1, c_2, ..., c_k-th columns respectively. A ball will stop dropping once it leaves the grid."633"Mr. Chanek wants to knit a batik, a traditional cloth from Indonesia. The cloth forms a grid a with size n × m. There are k colors, and each cell in the grid can be one of the k colors.634 635Define a sub-rectangle as an ordered pair of two cells ((x_1, y_1), (x_2, y_2)), denoting the top-left cell and bottom-right cell (inclusively) of a sub-rectangle in a. Two sub-rectangles ((x_1, y_1), (x_2, y_2)) and ((x_3, y_3), (x_4, y_4)) have the same pattern if and only if the following holds: 636 637 * they have the same width (x_2 - x_1 = x_4 - x_3); 638 * they have the same height (y_2 - y_1 = y_4 - y_3); 639 * for every pair (i, j) where 0 ≤ i ≤ x_2 - x_1 and 0 ≤ j ≤ y_2 - y_1, the color of cells (x_1 + i, y_1 + j) and (x_3 + i, y_3 + j) are equal. 640 641 642 643Count the number of possible batik color combinations, such that the subrectangles ((a_x, a_y),(a_x + r - 1, a_y + c - 1)) and ((b_x, b_y),(b_x + r - 1, b_y + c - 1)) have the same pattern.644 645Output the answer modulo 10^9 + 7.646 647Input648 649The first line contains five integers n, m, k, r, and c (1 ≤ n, m ≤ 10^9, 1 ≤ k ≤ 10^9, 1 ≤ r ≤ min(10^6, n), 1 ≤ c ≤ min(10^6, m)) — the size of the batik, the number of colors, and size of the sub-rectangle.650 651The second line contains four integers a_x, a_y, b_x, and b_y (1 ≤ a_x, b_x ≤ n, 1 ≤ a_y, b_y ≤ m) — the top-left corners of the first and second sub-rectangle. Both of the sub-rectangles given are inside the grid (1 ≤ a_x + r - 1, b_x + r - 1 ≤ n, 1 ≤ a_y + c - 1, b_y + c - 1 ≤ m).652 653Output654 655Output an integer denoting the number of possible batik color combinations modulo 10^9 + 7.656 657Examples658 659Input660 661 6623 3 2 2 26631 1 2 2664 665 666Output667 668 66932670 671 672Input673 674 6754 5 170845 2 26761 4 3 1677 678 679Output680 681 682756680455683 684Note685 686The following are all 32 possible color combinations in the first example.687 688<image>"689"Mr. Chanek gives you a sequence a indexed from 1 to n. Define f(a) as the number of indices where a_i = i. 690 691You can pick an element from the current sequence and remove it, then concatenate the remaining elements together. For example, if you remove the 3-rd element from the sequence [4, 2, 3, 1], the resulting sequence will be [4, 2, 1]. 692 693You want to remove some elements from a in order to maximize f(a), using zero or more operations. Find the largest possible f(a).694 695Input696 697The first line contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the initial length of the sequence.698 699The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 2 ⋅ 10^5) — the initial sequence a.700 701Output702 703Output an integer denoting the largest f(a) that can be obtained by doing zero or more operations.704 705Examples706 707Input708 709 71077112 1 4 2 5 3 7712 713 714Output715 716 7173718 719 720Input721 722 72347244 2 3 1725 726 727Output728 729 7302731 732Note733 734In the first example, f(A) = 3 by doing the following operations.735 736[2,1,4,2,5,3,7] → [2,1,2,5,3,7] → [1,2,5,3,7] → [1,2,5,3] → [1,2,3]737 738In the second example, f(A) = 2 and no additional operation is needed."739"Mr. Chanek's city can be represented as a plane. He wants to build a housing complex in the city.740 741There are some telephone poles on the plane, which is represented by a grid a of size (n + 1) × (m + 1). There is a telephone pole at (x, y) if a_{x, y} = 1.742 743For each point (x, y), define S(x, y) as the square of the Euclidean distance between the nearest pole and (x, y). Formally, the square of the Euclidean distance between two points (x_1, y_1) and (x_2, y_2) is (x_2 - x_1)^2 + (y_2 - y_1)^2.744 745To optimize the building plan, the project supervisor asks you the sum of all S(x, y) for each 0 ≤ x ≤ n and 0 ≤ y ≤ m. Help him by finding the value of ∑_{x=0}^{n} {∑_{y=0}^{m} {S(x, y)}}.746 747Input748 749The first line contains two integers n and m (0 ≤ n, m < 2000) — the size of the grid.750 751Then (n + 1) lines follow, each containing (m + 1) integers a_{i, j} (0 ≤ a_{i, j} ≤ 1) — the grid denoting the positions of telephone poles in the plane. There is at least one telephone pole in the given grid.752 753Output754 755Output an integer denoting the value of ∑_{x=0}^{n} {∑_{y=0}^{m} {S(x, y)}}.756 757Examples758 759Input760 761 7622 2763101764000765000766 767 768Output769 770 77118772 773 774Input775 776 7775 4778100107790000078001000781000017820010078300010784 785 786Output787 788 78936790 791Note792 793<image>794 795In the first example, the nearest telephone pole for the points (0,0), (1,0), (2,0), (0,1), (1,1), and (2,1) is at (0, 0). While the nearest telephone pole for the points (0, 2), (1,2), and (2,2) is at (0, 2). Thus, ∑_{x=0}^{n} {∑_{y=0}^{m} {S(x, y)}} = (0 + 1 + 4) + (1 + 2 + 5) + (0 + 1 + 4) = 18."796"Casimir has a string s which consists of capital Latin letters 'A', 'B', and 'C' only. Each turn he can choose to do one of the two following actions:797 798 * he can either erase exactly one letter 'A' and exactly one letter 'B' from arbitrary places of the string (these letters don't have to be adjacent); 799 * or he can erase exactly one letter 'B' and exactly one letter 'C' from arbitrary places in the string (these letters don't have to be adjacent). 800 801 802 803Therefore, each turn the length of the string is decreased exactly by 2. All turns are independent so for each turn, Casimir can choose any of two possible actions.804 805For example, with s = ""ABCABC"" he can obtain a string s = ""ACBC"" in one turn (by erasing the first occurrence of 'B' and the second occurrence of 'A'). There are also many other options for a turn aside from this particular example.806 807For a given string s determine whether there is a sequence of actions leading to an empty string. In other words, Casimir's goal is to erase all letters from the string. Is there a way to do this?808 809Input810 811The first line contains an integer t (1 ≤ t ≤ 1000) — the number of test cases.812 813Each test case is described by one string s, for which you need to determine if it can be fully erased by some sequence of turns. The string s consists of capital letters 'A', 'B', 'C' and has a length from 1 to 50 letters, inclusive.814 815Output816 817Print t lines, each line containing the answer to the corresponding test case. The answer to a test case should be YES if there is a way to fully erase the corresponding string and NO otherwise.818 819You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes, and YES will all be recognized as positive answers).820 821Example822 823Input824 825 8266827ABACAB828ABBA829AC830ABC831CABCBB832BCBCBCBCBCBCBCBC833 834 835Output836 837 838NO839YES840NO841NO842YES843YES"844"The new generation external memory contains an array of integers a[1 … n] = [a_1, a_2, …, a_n].845 846This type of memory does not support changing the value of an arbitrary element. Instead, it allows you to cut out any segment of the given array, cyclically shift (rotate) it by any offset and insert it back into the same place.847 848Technically, each cyclic shift consists of two consecutive actions: 849 850 1. You may select arbitrary indices l and r (1 ≤ l < r ≤ n) as the boundaries of the segment. 851 2. Then you replace the segment a[l … r] with it's cyclic shift to the left by an arbitrary offset d. The concept of a cyclic shift can be also explained by following relations: the sequence [1, 4, 1, 3] is a cyclic shift of the sequence [3, 1, 4, 1] to the left by the offset 1 and the sequence [4, 1, 3, 1] is a cyclic shift of the sequence [3, 1, 4, 1] to the left by the offset 2. 852 853 854 855For example, if a = [1, \color{blue}{3, 2, 8}, 5], then choosing l = 2, r = 4 and d = 2 yields a segment a[2 … 4] = [3, 2, 8]. This segment is then shifted by the offset d = 2 to the left, and you get a segment [8, 3, 2] which then takes the place of of the original elements of the segment. In the end you get a = [1, \color{blue}{8, 3, 2}, 5].856 857Sort the given array a using no more than n cyclic shifts of any of its segments. Note that you don't need to minimize the number of cyclic shifts. Any method that requires n or less cyclic shifts will be accepted.858 859Input860 861The first line contains an integer t (1 ≤ t ≤ 1000) — the number of test cases.862 863The next 2t lines contain the descriptions of the test cases. 864 865The first line of each test case description contains an integer n (2 ≤ n ≤ 50) — the length of the array. The second line consists of space-separated elements of the array a_i (-10^9 ≤ a_i ≤ 10^9). Elements of array a may repeat and don't have to be unique.866 867Output868 869Print t answers to all input test cases. 870 871The first line of the answer of each test case should contain an integer k (0 ≤ k ≤ n) — the number of actions to sort the array. The next k lines should contain descriptions of the actions formatted as ""l r d"" (without quotes) where l and r (1 ≤ l < r ≤ n) are the boundaries of the segment being shifted, while d (1 ≤ d ≤ r - l) is the offset value. Please remember that only the cyclic shifts to the left are considered so the chosen segment will be shifted by the offset d to the to the left.872 873Note that you are not required to find the minimum number of cyclic shifts needed for sorting. Any sorting method where the number of shifts does not exceed n will be accepted.874 875If the given array a is already sorted, one of the possible answers is k = 0 and an empty sequence of cyclic shifts.876 877If there are several possible answers, you may print any of them.878 879Example880 881Input882 883 884488528862 188738881 2 188948902 4 1 389158922 5 1 4 3893 894 895Output896 897 89818991 2 190019011 3 290239032 4 19042 3 19051 3 290649072 4 29081 5 39091 2 19101 3 1911 912Note913 914Explanation of the fourth data set in the example: 915 916 1. The segment a[2 … 4] is selected and is shifted to the left by 2: [2, \color{blue}{5, 1, 4}, 3] \longrightarrow [2, \color{blue}{4, 5, 1}, 3] 917 2. The segment a[1 … 5] is then selected and is shifted to the left by 3: [\color{blue}{2, 4, 5, 1, 3}] \longrightarrow [\color{blue}{1, 3, 2, 4, 5}] 918 3. After that the segment a[1 … 2] is selected and is shifted to the left by 1: [\color{blue}{1, 3}, 2, 4, 5] \longrightarrow [\color{blue}{3, 1}, 2, 4, 5] 919 4. And in the end the segment a[1 … 3] is selected and is shifted to the left by 1: [\color{blue}{3, 1, 2}, 4, 5] \longrightarrow [\color{blue}{1, 2, 3}, 4, 5] "920"Casimir has a rectangular piece of paper with a checkered field of size n × m. Initially, all cells of the field are white.921 922Let us denote the cell with coordinates i vertically and j horizontally by (i, j). The upper left cell will be referred to as (1, 1) and the lower right cell as (n, m).923 924Casimir draws ticks of different sizes on the field. A tick of size d (d > 0) with its center in cell (i, j) is drawn as follows: 925 926 1. First, the center cell (i, j) is painted black. 927 2. Then exactly d cells on the top-left diagonally to the center and exactly d cells on the top-right diagonally to the center are also painted black. 928 3. That is all the cells with coordinates (i - h, j ± h) for all h between 0 and d are painted. In particular, a tick consists of 2d + 1 black cells. 929 930 931 932An already painted cell will remain black if painted again. Below you can find an example of the 4 × 9 box, with two ticks of sizes 2 and 3.933 934<image>935 936You are given a description of a checkered field of size n × m. Casimir claims that this field came about after he drew some (possibly 0) ticks on it. The ticks could be of different sizes, but the size of each tick is at least k (that is, d ≥ k for all the ticks).937 938Determine whether this field can indeed be obtained by drawing some (possibly none) ticks of sizes d ≥ k or not.939 940Input941 942The first line contains an integer t (1 ≤ t ≤ 100) — the number test cases.943 944The following lines contain the descriptions of the test cases. 945 946The first line of the test case description contains the integers n, m, and k (1 ≤ k ≤ n ≤ 10; 1 ≤ m ≤ 19) — the field size and the minimum size of the ticks that Casimir drew. The following n lines describe the field: each line consists of m characters either being '.' if the corresponding cell is not yet painted or '*' otherwise.947 948Output949 950Print t lines, each line containing the answer to the corresponding test case. The answer to a test case should be YES if the given field can be obtained by drawing ticks of at least the given size and NO otherwise.951 952You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes, and YES will all be recognized as positive answers).953 954Example955 956Input957 958 95989602 3 1961*.*962...9634 9 2964*.*.*...*965.*.*...*.966..*.*.*..967.....*...9684 4 1969*.*.970****971.**.972....9735 5 1974.....975*...*976.*.*.977..*.*978...*.9795 5 2980.....981*...*982.*.*.983..*.*984...*.9854 7 1986*.....*987.....*.988..*.*..989...*...9903 3 1991***992***993***9943 5 1995*...*996.***.997.**..998 999 1000Output1001 1002 1003NO1004YES1005YES1006YES1007NO1008NO1009NO1010NO1011 1012Note1013 1014The first sample test case consists of two asterisks neither of which can be independent ticks since ticks of size 0 don't exist.1015 1016The second sample test case is already described in the statement (check the picture in the statement). This field can be obtained by drawing ticks of sizes 2 and 3, as shown in the figure.1017 1018The field in the third sample test case corresponds to three ticks of size 1. Their center cells are marked with \color{blue}{blue}, \color{red}{red} and \color{green}{green} colors: *.*. 1019--- 1020*\color{blue}{*}** 1021.\color{green}{*}\color{red}{*}. 1022.... 1023 1024The field in the fourth sample test case could have been obtained by drawing two ticks of sizes 1 and 2. Their vertices are marked below with \color{blue}{blue} and \color{red}{red} colors respectively: ..... 1025--- 1026*...* 1027.*.*. 1028..\color{red}{*}.* 1029...\color{blue}{*}. 1030 1031The field in the fifth sample test case can not be obtained because k = 2, and the last asterisk in the fourth row from the top with coordinates (4, 5) can only be a part of a tick of size 1.1032 1033The field in the sixth sample test case can not be obtained because the top left asterisk (1, 1) can't be an independent tick, since the sizes of the ticks must be positive, and cannot be part of a tick with the center cell in the last row, since it is separated from it by a gap (a point, '.') in (2, 2).1034 1035In the seventh sample test case, similarly, the field can not be obtained by the described process because the asterisks with coordinates (1, 2) (second cell in the first row), (3, 1) and (3, 3) (leftmost and rightmost cells in the bottom) can not be parts of any ticks."1036"An important meeting is to be held and there are exactly n people invited. At any moment, any two people can step back and talk in private. The same two people can talk several (as many as they want) times per meeting.1037 1038Each person has limited sociability. The sociability of the i-th person is a non-negative integer a_i. This means that after exactly a_i talks this person leaves the meeting (and does not talk to anyone else anymore). If a_i = 0, the i-th person leaves the meeting immediately after it starts.1039 1040A meeting is considered most productive if the maximum possible number of talks took place during it.1041 1042You are given an array of sociability a, determine which people should talk to each other so that the total number of talks is as large as possible.1043 1044Input1045 1046The first line contains an integer t (1 ≤ t ≤ 1000) — the number of test cases.1047 1048The next 2t lines contain descriptions of the test cases.1049 1050The first line of each test case description contains an integer n (2 ≤ n ≤ 2 ⋅ 10^5) —the number of people in the meeting. The second line consists of n space-separated integers a_1, a_2, ..., a_n (0 ≤ a_i ≤ 2 ⋅ 10^5) — the sociability parameters of all people. 1051 1052It is guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 10^5. It is also guaranteed that the sum of all a_i (over all test cases and all i) does not exceed 2 ⋅ 10^5.1053 1054Output1055 1056Print t answers to all test cases.1057 1058On the first line of each answer print the number k — the maximum number of talks possible in a meeting.1059 1060On each of the next k lines print two integers i and j (1 ≤ i, j ≤ n and i ≠ j) — the numbers of people who will have another talk.1061 1062If there are several possible answers, you may print any of them.1063 1064Example1065 1066Input1067 1068 106981070210712 31072310731 2 31074410751 2 3 41076310770 0 21078210796 21080310810 0 21082510838 2 0 1 11084510850 1 0 0 61086 1087 1088Output1089 1090 1091210921 210931 21094310951 310962 310972 31098510991 311002 411012 411023 411033 4110401105211061 211071 2110801109411101 211111 511121 411131 21114111155 2"1116"In fact, the problems E1 and E2 do not have much in common. You should probably think of them as two separate problems.1117 1118You are given an integer array a[1 … n] = [a_1, a_2, …, a_n].1119 1120Let us consider an empty [deque](https://tinyurl.com/pfeucbux) (double-ended queue). A deque is a data structure that supports adding elements to both the beginning and the end. So, if there are elements [3, 4, 4] currently in the deque, adding an element 1 to the beginning will produce the sequence [\color{red}{1}, 3, 4, 4], and adding the same element to the end will produce [3, 4, 4, \color{red}{1}].1121 1122The elements of the array are sequentially added to the initially empty deque, starting with a_1 and finishing with a_n. Before adding each element to the deque, you may choose whether to add it to the beginning or to the end.1123 1124For example, if we consider an array a = [3, 7, 5, 5], one of the possible sequences of actions looks like this: 1. | add 3 to the beginning of the deque: | deque has a sequence [\color{red}{3}] in it; 1125---|---|--- 1126 2. | add 7 to the end of the deque: | deque has a sequence [3, \color{red}{7}] in it; 1127 3. | add 5 to the end of the deque: | deque has a sequence [3, 7, \color{red}{5}] in it; 1128 4. | add 5 to the beginning of the deque: | deque has a sequence [\color{red}{5}, 3, 7, 5] in it; 1129 1130Find the minimal possible number of inversions in the deque after the whole array is processed. 1131 1132An inversion in sequence d is a pair of indices (i, j) such that i < j and d_i > d_j. For example, the array d = [5, 3, 7, 5] has exactly two inversions — (1, 2) and (3, 4), since d_1 = 5 > 3 = d_2 and d_3 = 7 > 5 = d_4.1133 1134Input1135 1136The first line contains an integer t (1 ≤ t ≤ 1000) — the number of test cases.1137 1138The next 2t lines contain descriptions of the test cases. 1139 1140The first line of each test case description contains an integer n (1 ≤ n ≤ 2 ⋅ 10^5) — array size. The second line of the description contains n space-separated integers a_i (-10^9 ≤ a_i ≤ 10^9) — elements of the array.1141 1142It is guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 10^5.1143 1144Output1145 1146Print t lines, each line containing the answer to the corresponding test case. The answer to a test case should be a single integer — the minimal possible number of inversions in the deque after executing the described algorithm.1147 1148Example1149 1150Input1151 1152 115361154411553 7 5 51156311573 2 11158311593 1 2116041161-1 2 2 -11162411634 5 1 31164511651 3 1 3 21166 1167 1168Output1169 1170 1171211720117311174011751117621177 1178Note1179 1180One of the ways to get the sequence [5, 3, 7, 5] in the deque, containing only two inversions, from the initial array [3, 7, 5, 5] (the first sample test case) is described in the problem statement. 1181 1182Also, in this example, you could get the answer of two inversions by simply putting each element of the original array at the end of the deque. In this case, the original sequence [3, 7, 5, 5], also containing exactly two inversions, will be in the deque as-is."1183"You are given an array a[0 … n - 1] = [a_0, a_1, …, a_{n - 1}] of zeroes and ones only. Note that in this problem, unlike the others, the array indexes are numbered from zero, not from one.1184 1185In one step, the array a is replaced by another array of length n according to the following rules: 1186 1187 1. First, a new array a^{→ d} is defined as a cyclic shift of the array a to the right by d cells. The elements of this array can be defined as a^{→ d}_i = a_{(i + n - d) mod n}, where (i + n - d) mod n is the remainder of integer division of i + n - d by n. 1188 1189It means that the whole array a^{→ d} can be represented as a sequence $$$a^{→ d} = [a_{n - d}, a_{n - d + 1}, …, a_{n - 1}, a_0, a_1, …, a_{n - d - 1}]$$$1190 1191 2. Then each element of the array a_i is replaced by a_i \& a^{→ d}_i, where \& is a logical ""AND"" operator. 1192 1193 1194 1195For example, if a = [0, 0, 1, 1] and d = 1, then a^{→ d} = [1, 0, 0, 1] and the value of a after the first step will be [0 \& 1, 0 \& 0, 1 \& 0, 1 \& 1], that is [0, 0, 0, 1].1196 1197The process ends when the array stops changing. For a given array a, determine whether it will consist of only zeros at the end of the process. If yes, also find the number of steps the process will take before it finishes.1198 1199Input1200