Write a templated function that performs in-place quick-sorting using random partitioning. It should accept custom compare functions.

There are coins on the road. Each coin has a position (determined by a single integer number - the distance in metres from some origin). Every coin is located on one side of that origin. Robin Hood starts wherever he wants and collects these coins. He goes 1 metre per second. Each coin has a timer in seconds after which it expires (strictly after). Robin Hood is determined to collect them all.
The first line of the input contains the number n (1 ≤ n ≤ 1000). The following n lines contain 2 integers - position and expiration time. Positions are integers between 0 and 1000000. Timers are integers between 0 and 1000000. The output should contain one number - the minimum time required to collect every single coin. If the task is not possible, simply output '-1'.

Time complexity: O(n²)

You want to build a football team. Every player has his performance described by an integer. The greater the number, the more effective the player is. Every team should be solid. If one of the players plays much better than all others, then other team members will dislike him, and the team will not be solid. Thus, the performance of every team member should not exceed the sum of performances of any two other team members.
Your task is to assemble a solid team with maximum total performance (which is the sum of performances of all players). The first line of the input contains the number n (1 ≤ n ≤ 100000). The second line contains the performances of every of the n players. Performances are positive integers not greater than 2³¹-1. The output should contain two lines. The first line should contain the maximum total performance of the team you can build from given players. The second line should contain the numbers of the players (in ascending order) that you need to put to your team in order to reach this performance. The players have numbers starting from 1 to n in the same order that their performances appear in the input. If there are several ways to build the team, output any of them.

Time complexity: O(n*log(n))

You have n triangles (1 ≤ n ≤ 1000000). Every one of them is defined by its 3 sides - using 3 integers not greater than 10⁹. Some of them are similar. Let us say that two triangles are different if they are not similar. How many different triangles do you have?
The first line of the input contains the number n. The following n lines contain 3 integers that define triangles. The output should contain a single number - number of different triangles.

Time complexity: O(n)

Create a class defining AVL Tree. Define the following operations: insert, get, erase, print.

Create calculator interpreter. It should accept a single line containing only the following symbols:
0 1 2 3 4 5 6 7 8 9 . e ( ) - + * / ^ !
The output should contain a result, or 'error' in case of invalid input expression.