Quick sort

ID 31926. Snowflake classification

ID 34879. K-quest

In one of the computer quest games there is the following task. There are N characters on the map of the game world, each of which the player can meet. From communication with the i-th character, the player's karma changes by the value ai, which can be either positive or negative or even zero.

Initially, the player's karma is zero. In order to pass to the next level, you need to have karma exactly equal to the value of K, while karma can also take both positive and negative values.

The rooms where the characters are located are connected by one-way magical portals, so the player will have to meet the characters in a certain sequence: after the character number i, he gets to the character number i + 1, then to the character number i + 2, and so on. .d. There is no portal to another character in the room of the last character with number N.

To move between characters, you can also use teleportation spells, but unfortunately the hero has only two scrolls with spells left. Therefore, one of these scrolls will have to be used in order to teleport to any of the characters, and the second scroll — to leave the game world after the hero's karma reaches K.

Help the player determine which room to teleport to at the beginning and which room to leave the game world to reach Karma K, or tell them it's not possible.

Input
The first line of the input contains two numbers: the number of characters N and the required level of karma K (|K| ≤ 109, K ≠ 0). The second line contains N space-separated integers a1, a2, ..., aN — values ​​by which the hero's karma changes after communicating with characters with numbers 1, 2, ..., N, respectively.

Imprint
Print the number of the room the player must enter and the number of the room from which the player must exit in order to collect karma K. big number. If it is impossible to achieve karma K by consistently communicating with the characters, then print a single number  - 1.
 

ID 22008. Big sort

Examples

ID 31880. Fence painting

One day, as punishment for pranks and deceit, Aunt Polly made Tom paint a L yard fence. All of you remember very well that Tom sold (for various goodies) his work to other boys who wanted to whitewash the fence.
By the time Tom ran out of lime, the fence had been painted by N boys. And since Tom didn’t really follow the boys, everyone painted the part of the fence that he liked best. 
Each i-th boy started painting the fence from a vertical plank with coordinate Lefti and painted up to plank with coordinate Righti (the length of the board is considered equal to 1). 
Determine the length of the fence that Tom will need to paint himself. 

 

Examples

ID 37257. Taxi

After a long meeting, the director of the company decided to order a taxi to take the employees home. He ordered N cars  – as many as it has employees. However, when they arrived, it turned out that each taxi driver has his own tariff for 1 kilometer.

The director knows which employee how many kilometers from work to home (unfortunately, all employees live in different directions, so you cannot send two employees in one car). Now the director wants to determine which of the employees should take which taxi home so that the total cost of a taxi (and they are borne by the company) is minimal.

ID 37256. Rescuing robots

A storm of diamond dust has risen on Shelezyak's planet. As you know, diamond dust causes paralysis in robots. At the beginning of the storm, all the robots were busy working along one straight road. There are m repair shops along the same road. Therefore, it was decided to send each robot to the nearest repair shop to renew their lubricant. 
It is necessary for each robot to determine the nearest repair shop to it.
 

Examples

ID 37258. bomb shelters

The Civil Defense Headquarters of the Thirtieth Region decided to update the rescue plan in case of a nuclear attack. It is known that all n villages of the Thirtieth Region are located along one straight road. There are also m bomb shelters along the road, where villagers can take shelter in case of a nuclear attack.

In order for the rescue in the event of a nuclear alarm to be as efficient as possible, it is necessary to determine the nearest bomb shelter for each village.

ID 31879. Anti-QuickSort (under development)

You are given a number N (1<=N<=1000) and then N natural numbers from the range 1 to 100.
Output a permutation of array elements on which quicksort will perform the maximum number of comparisons, provided that the "reference" there will be an element in the middle. 

Input: number N is given in the first line
The second line contains N numbers - array elements
Output: print the desired permutation of the elements of the original array

Examples

ID 37691. Anti-QuickSort

Given a number N (\(1<=N<=1000\)) followed by N natural numbers from 1 to 100.
Output the permutation of the array elements on which quicksort will perform the maximum number of comparisons, provided that "reference" there will be an element in the middle. 

Input  
The first line specifies the number N.

Imprint
Output the desired permutation of numbers from 1 to N, on which quicksort will perform the maximum number of comparisons.
 

Examples

Explanation

ID 38920. elves and deer

The New Year is coming soon and Santa Claus has already started preparing his magical reindeer team, on which he delivers gifts to children. It is known that the team is driven by several magical deer, each of which is ridden by two elves.

But the magical deer – obstinate animals, so not any two elves can ride any deer. Namely, each deer is characterized by some obstinacy a_i, and each elf – temperament b_i. Two elves j and k can ride the i-th reindeer if and only if either b_j < a_i < b_k or b_k < a_i < b_j.

To make his appearance as spectacular as possible, Santa Claus wants his team to have as many reindeer as possible. About every deer Santa knows his obstinacy, and about every elf – his temperament.

Help Santa figure out the maximum number of reindeer he can include in his team, which reindeer he should choose, and which elves should ride them.

Input
The first line contains two integers m and n – the number of deer and elves, respectively ( 1 ≤ m, n ≤ 100,000).

The second line contains m integers ai – deer obstinacy ( 0 ≤ a_i ≤ 10⁹). The third line contains n integers bi – elves temperament ( 0 ≤ b_i ≤ 10⁹).

Imprint
In the first line  print a single number k – the maximum number of reindeer that Santa Claus can include in his team. In the next k lines print three integers each: d_i, e_i, 1, e_i, 2 – for each reindeer in the team print its number and the numbers of the elves that will ride it. If there are several solutions, print any one.

Both elves and deer are numbered, starting from one, in the order in which they are given in the input.

Examples

ID 38991. Advertising 2

The supermarket decided to broadcast advertisements for new products from time to time. In order to create the optimal schedule for broadcasting advertising, the supermarket management conducted the following study: during the day, for each customer who visited the supermarket, the time when he arrived at the supermarket and when he left it was recorded.

The advertising manager assumed that such a schedule of arrivals and departures of buyers would continue in the following days. He wants to schedule commercials so that each customer hears at least two advertisements. At the same time, he stipulated that two advertisements should not be broadcast at the same time and, since the sellers had to listen to these advertisements all the time, the total number of advertisements per day was minimal.

Write a program that will create such a schedule for broadcasting commercials. Advertisements can start broadcasting only at whole points in time. Each advertisement is considered to end before the next integer point in time. If an advertisement is broadcast at the moment when the customer enters or leaves the supermarket, the customer has time to hear this advertisement.

Input
The input file contains first the number N — number of shoppers visiting the supermarket per day (1<N<3000). Then comes N pairs of natural numbers Ai, Bi, specifying the time of arrival and departure of customers from the supermarket, respectively (0<A_i<B_i<106).

Imprint
In the output file, first print the number of advertisements that will be broadcast per day. Then output in ascending order the time points at which you want to broadcast advertisements.

If there are several solutions, print any of them.
 

Examples