You have been hired as a gardener for Queen Bajtolina. Sounds great, right? If you think so, you probably don't know everything about this job yet. Next to the Queen's castle is a large garden with $n$ trees planted in a row, one after another. That is not the worst part, but can you answer your ruler at any time of the day or night which of her trees are currently mature? We assume a tree is mature if it is at least $k$ "bajtimeters" tall.

Sometimes the Queen asks you to water some of her trees using a magic watering can. Each such operation causes all watered trees to grow by exactly one bajtimeter.

Prove that you are suitable for this job and quickly answer all the Queen's questions!

Interaction

Write a library that communicates with the grading program. It should contain at least the following three functions, called by the grading program:

• inicjuj(n, k, D) – this function will be called exactly once, at the beginning of the check. You can use it to initialize your data structures. It takes as parameters the number of trees $n$, the lower bound of the height of a mature tree $k$, and an array $D$ of length $n$ containing the initial heights of all trees. The trees are numbered with consecutive integers from $0$ to $n - 1$.
  • C/C++: void inicjuj(int n, int k, int *D);
  • Pascal: procedure inicjuj(n, k : LongInt; var D : array of LongInt);
• podlej(a, b) – means that the Queen has asked you to water all trees from the $a$-th to the $b$-th inclusive ($0 \le a \le b \le n - 1$). Calling this procedure/function means that each of these trees grows by $1$ bajtimeter.
  • C/C++: void podlej(int a, int b);
  • Pascal: procedure podlej(a, b : LongInt);
• dojrzale(a, b) – the Queen asks you how many of the trees numbered from $a$ to $b$ inclusive ($0 \le a \le b \le n - 1$) are already mature.
  • C/C++: int dojrzale(int a, int b);
  • Pascal: function dojrzale(a, b : LongInt) : LongInt;

Your library must not read any data (neither from standard input nor from files). It also must not write anything to files or standard output. It may write to the standard diagnostic output (stderr) – however, remember that this consumes valuable time.

If you are writing in C/C++, your library must not contain the main function. If you are writing in Pascal, you should provide a module.

Your solution will receive points for a given test only if it meets the technical requirements specified above and answers all the Queen's questions correctly.

Constraints

In all tests, the following conditions hold:

• $1 \le n \le 300\,000$
• $1 \le k \le 10^9$
• The total number of calls to the podlej procedure/function and the dojrzale function does not exceed $300\,000$
• The initial heights of all trees are positive integers not exceeding $10^9$

In tests worth a total of 20% of the points, additional conditions hold:

• $n \le 2\,000$
• The total number of calls to the podlej procedure/function and the dojrzale function does not exceed $10\,000$

In tests worth a total of 50% of the points, all calls to the podlej procedure/function occur before all calls to the dojrzale function.

Examples

Input 1

inicjuj(4, 6, D) // D = {5, 4, 3, 7}
dojrzale(2, 3)
podlej(0, 2)
dojrzale(1, 2)
podlej(2, 3)
podlej(0, 1)
dojrzale(0, 3)

Output 1

1
0
3

Note

The example shows a sequence of calls. Initially, we have $n = 4$ trees with heights 5, 4, 3, and 7, and $k = 6$. The first call to dojrzale(2, 3) checks trees at indices 2 and 3 (heights 3 and 7), where only one is mature. After podlej(0, 2), trees 0, 1, and 2 grow by 1. Subsequent calls continue to track the number of mature trees.