Arithmetic Algorithms

ID 31849. Irreducible fractions

Examples

ID 38326. Dominoes

Consider N-dominoes. In such a domino, each domino consists of two halves, each of which is drawn from 0 to N dots. A complete set of bones of such a domino contains all possible bones, each — once. For example, for N=2, the set will include the following tiles: (0.0), (0.1), (0.2), (1.1), (1.2) and (2.2)

Write a program that, given N, will determine how many dots are shown on all tiles of a complete set of N-dominoes.

Input
A natural number N is entered (1<=N<=30).

Imprint
The program should print one number - the total number of dots on all tiles of a complete set of N-dominoes.

Examples

ID 38503. Candy for children

At the children's holiday, the children led round dances. Once the music had finished playing, the children were still standing in the circle. Then Lena remembered that her parents had given her a box of k Wilky May sweets. Lena is not greedy, so she decided to give all her sweets to friends from the round dance. Lena knows that some of her friends have a sweet tooth and some don't. Those with a sweet tooth take two candies from the box if there are at least two candies in the box, otherwise they take one. Lena's other friends always take exactly one candy from the box.

To start handing out sweets, Lena left the round dance, after which n of her friends remained in the round dance. To make it easier to hand out sweets, Lena assigned a number to each friend in the round dance, in clockwise order, starting with her best friend Roma, who received number 1.

Lena gave the box to a friend who received number l, after which each friend of Lena, starting with friend number l, took sweets from the box and passed the box to the next friend in clockwise order. After the friend with the number r took the candies, there were no candies left in the box. Please note that it is possible that some of Lena's friends took candies from the box several times, that is, the box could go several full circles in a round dance.

Lena does not know which of her friends have a sweet tooth, but she is interested in how many of her friends can have a sweet tooth. If such a situation could not happen, and Lena made a mistake in her observations, tell her about it.

Input
A single line contains four integers n, l, r, k (1 ≤ n, k ≤ 10¹¹ , 1 ≤ l, r ≤ n ) — the number of children in the round dance, the number of the friend to whom Lena gave the box of chocolates, the number of the friend who took the last candy, and the number of candies in the box, respectively.

Imprint
Print a single integer — the maximum possible number of sweet teeth among Lena's friends or « -1 " (without quotes) if Lena made a mistake in her observations.
 

Examples

ID 42263. dragon curve

Today the boy Sasha learned about fractals at a mathematics lesson. The teacher showed the so-called "dragon curve". It is a geometric figure, which is constructed as follows: at the first step, a segment is drawn from the origin of the coordinate plane to the point (0; 1). Further, at each step from the end of the fractal, the already drawn part of the figure is repeated, rotated 90 degrees counterclockwise (see figure).

After the lessons, Sasha tried to draw the "dragon curve" himself, and now he wants to know at what point on the coordinate plane he finished drawing the fractal by following the N steps described above. It is required to write a program that, given the number of N determines the coordinates of the end of the fractal after performing N steps.

Examples