Currently, evaluating the significance of license plates, phone numbers, birth dates, or any sequence of digits is of interest to many people. The way to assess the beauty of a sequence of numbers is as follows: Calculate the sum of the digits in the sequence. If the sum is a single-digit number, that is the beauty value (beauty score) of the sequence. Otherwise, continue calculating the sum of the digits until you get a single-digit number.

Example:

• For the birth date sequence 02022020, the sum of the digits is 8, so the beauty score of the sequence is 8.
• For the phone number 0912345678, the sum of the digits is 45. Continuing to calculate the sum gives 9, so the beauty score of the sequence is 9.

Requirement:

• Given a sequence with ~ n~ digits, evaluate the beauty score of the given sequence.

Input

• Contains a sequence with ~ n ~ digits (~ n \leq 10^5 ~).

Output

• An integer representing the beauty score of the sequence.

Sample Input

02022020

Sample Output

8

Bob loves solving number puzzles. After learning how to find the K-th smallest number in a sorted list, he now wants a bigger challenge.

This time, Bob wants to find the ~K-th~ smallest positive number that is not in his list.

The list contains distinct positive integers in increasing order. Some numbers are missing from the natural counting sequence, and Bob wants to find the one that comes ~K-th~ among those missing numbers.

Your task is to help Bob find the ~K-th~ missing number from a sorted list.

Input

• The first line contains a single integer ~N (1 ≤ N ≤ 10^5)~ — the number of distinct integers in the list.
• The second line contains ~N~ distinct positive integers: ~a_1, a_2, ..., a_n~ ~(1 ≤ a_1 < a_2 < ... < a_n ≤ 10^6)~, sorted in ascending order.
• The third line contains a single integer ~K (1 ≤ K ≤ 10^6)~ — the K-th missing number to find.

Output

• Print the ~K-th~ missing number.

📌 Example

Input

4  
3 5 6 7  
3

Output

4

💡 Explanation

The list is A = [3, 5, 6, 7].

The missing positive numbers are:
1, 2, 4, 8, 9, ...

The 3nd missing number is 4, so the answer is 4.

Given a positive integer ~𝑛~, count how many positive divisors of ~𝑛~ have exactly ~4~ positive divisors.

Input:

• A single line containing the positive integer ~𝑛~. ~(𝑛 ≤ 10^{10})~

Output:

• A single integer representing the result.

Sample Input

8

Sample Output

1

Bob breezed through the Missing Number 1 challenge, but that was too boring for him. So, he cranked up the difficulty: more numbers, more queries, and an even bigger challenge!

Now, he is on a new quest to find the ~K-th~ missing number, and he dared you to solve it faster than ever before.

Again, The list will contains distinct positive integers in increasing order. Some numbers are missing from the natural counting sequence, and Bob wants to find the one that comes ~K-th~ among those missing numbers.

Your task is to find the ~K-th~ missing number from a sorted list with new challenge!.

Input

• The first line contains two integers ~N~ and ~Q~ ~(1 ≤ N, Q ≤ 10^5)~. — ~N~ is the number of integers in the sorted list and ~Q~ is the number of queries Bob has.
• The second line contains ~N~ distinct positive integers: ~a_1, a_2, ..., a_n~ ~(1 ≤ a_1 < a_2 < ... < a_n ≤ 10^{18})~, sorted in ascending order.
• The next ~Q~ lines each contain a single integer ~K_i (1 ≤ K_i ≤ 10^{18})~ - For each Query, Bob wants to find the ~K-th~ missing positive integer that is not in the list.

Output

• Print ~Q~ lines, where the ~i-th~ line is the answer to the ~i-th~ query — the ~K_i-th~ missing number not in Bob list.

📌 Example

Input

4 3  
3 5 6 7  
2  
9  
4

Output

2
13
8

There are ~ N ~ stones numbered ~ 1, 2, 3, ..., N ~. The height of the ~ i ~-th stone is ~ h_i ~.

A frog starts on stone ~ 1 ~. It can jump to any of the next ~ K ~ stones (~ i+1~ to ~ i+K ~), with a cost of ~ |h_i - h_j| ~, where ~ j ~ is the stone it wants to jump to.

Find the minimum cost for the frog to reach stone ~N ~.

Input

• The first line contains two integers ~N ~ and ~ K~ (~ 2 \leq N \leq 10^5 ~, ~ 1 \leq K \leq 100 ~).
• The second line contains ~ N ~ integers ~ h_1, h_2, ..., h_N ~ (~ 1 \leq h_i \leq 10^5 ~).

Output

• Print the minimum cost required.

Sample Input

5 3
10 30 40 50 20

Sample Output

30

Notes

• Con ếch sẽ nhảy như sau: ~1→2→5~,

To prepare for the rainy season, a group of engineers is reinforcing a series of water reservoirs on an island. The reservoirs are formed by natural rock columns arranged in a straight line. Each column has an initial height, and when it rains, water collects between the columns, creating storage areas like small basins.

To improve the reservoirs water capacity, the engineers are allowed to reinforce the rock columns by placing up to ~K~ unit-sized stone blocks. Each block increases the height of a column by 1 unit.

Water is retained only if it is trapped between taller columns on both sides. If water overflows a column, it is lost. Therefore, the goal is to carefully choose where to place the ~K~ blocks to maximize the total volume of water that can be held after reinforcement

Your task is to determine the maximum amount of water that can be stored after placing exactly ~K~ blocks in the most optimal way.

Input

• The first line contains two integers ~N~ and ~K~ ~(1 ≤ N, K ≤ 12)~ — the number of columns of rock and the number of available blocks.
• The second line contains ~N~ integers ~h_1, h_2,..., h_n ~ ~(1 ≤ h_i ≤ 10^{18})~ — the initial heights of the columns of rock.

Output

• A single integer — the maximum volume of water that can be stored after adding ~K~ blocks optimally.

📌 Example

Input

10 2
3 1 4 1 2 1 1 4 2 1

Output

17

💡 Explanation

This is the initial reservoir, which can store 13 blocks of water.

After placing up to ~K~ stone blocks (yellow blocks), the new reservoir can store ~4~ more blocks of water (green blocks).

So, the maximum volume of water that can be stored after adding ~2~ blocks optimally is 17 blocks of water.