Codeforces Round #450~#451 嘴炮AC

本文主要是介绍Codeforces Round #450~#451 嘴炮AC，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

补期末考试欠的账

You are given a permutation p of length n. Remove one element from permutation to make the number of records the maximum possible.

We remind that in a sequence of numbers a1, a2, ..., ak the element ai is a record if for every integer j(1 ≤ j < i) the following holds: aj < ai.

Input

The first line contains the only integer n (1 ≤ n ≤ 105) — the length of the permutation.

The second line contains n integers p1, p2, ..., pn (1 ≤ pi ≤ n) — the permutation. All the integers are distinct.

Output

Print the only integer — the element that should be removed to make the number of records the maximum possible. If there are multiple such elements, print the smallest one.

Examples 
input 
1
1
output 
1
input 
5
5 1 2 3 4
output 
5

Note

In the first example the only element can be removed.

http://codeforces.com/contest/900/problem/C

记录每个位置之前最大的两个数和对应位置，比较一下可以得到删去最大的数时，当前位置上的数是否会成为一个record。如果是就把最大的数的位置的贡献+1.扫一遍就可以。复杂度O(n)

Vasya wrote down two strings s of length n and t of length m consisting of small English letters 'a' and 'b'. What is more, he knows that string t has a form "abab...", namely there are letters 'a' on odd positions and letters 'b' on even positions.

Suddenly in the morning, Vasya found that somebody spoiled his string. Some letters of the string s were replaced by character '?'.

Let's call a sequence of positions i, i + 1, ..., i + m - 1 as occurrence of string t in s, if 1 ≤ i ≤ n - m + 1and t1 = si, t2 = si + 1, ..., tm = si + m - 1.

The boy defines the beauty of the string s as maximum number of disjoint occurrences of string t in s. Vasya can replace some letters '?' with 'a' or 'b' (letters on different positions can be replaced with different letter). Vasya wants to make some replacements in such a way that beauty of string s is maximum possible. From all such options, he wants to choose one with the minimum number of replacements. Find the number of replacements he should make.

Input

The first line contains a single integer n (1 ≤ n ≤ 105) — the length of s.

The second line contains the string s of length n. It contains small English letters 'a', 'b' and characters '?' only.

The third line contains a single integer m (1 ≤ m ≤ 105) — the length of t. The string t contains letters 'a' on odd positions and 'b' on even positions.

Output

Print the only integer — the minimum number of replacements Vasya has to perform to make the beauty of string s the maximum possible.

Examples 
input 
5
bb?a?
1
output 
2
input 
9
ab??ab???
3
output 
2

Note

In the first sample string t has a form 'a'. The only optimal option is to replace all characters '?' by 'a'.

In the second sample using two replacements we can make string equal to "aba?aba??". It is impossible to get more than two occurrences.

http://codeforces.com/contest/900/problem/E

一个显而易见的DP方程：

dp[i][j]=min( dp[i-1][j],dp[i-m][j-1]+cost(i-n+1,i) )

然后可以发现，可以把DP降维。把dp变成一个二元组(出现次数,cost)，优先比较出现次数再比较cost,可得

dp[i]=best( dp[i-1],dp[i-m]+cost(i-n+1,i) )

而这一运算可以通过重载operator实现

A correct expression of the form a+b=c was written; a, b and c are non-negative integers without leading zeros. In this expression, the plus and equally signs were lost. The task is to restore the expression. In other words, one character '+' and one character '=' should be inserted into given sequence of digits so that:

character'+' is placed on the left of character '=',
characters '+' and '=' split the sequence into three non-empty subsequences consisting of digits (let's call the left part a, the middle part — b and the right part — c),
all the three parts a, b and c do not contain leading zeros,
it is true that a+b=c.

It is guaranteed that in given tests answer always exists.

Input

The first line contains a non-empty string consisting of digits. The length of the string does not exceed 106.

Output

Output the restored expression. If there are several solutions, you can print any of them.

Note that the answer at first should contain two terms (divided with symbol '+'), and then the result of their addition, before which symbol'=' should be.

Do not separate numbers and operation signs with spaces. Strictly follow the output format given in the examples.

If you remove symbol '+' and symbol '=' from answer string you should get a string, same as string from the input data.

Examples 
input 
12345168
output 
123+45=168
input 
099
output 
0+9=9
input 
199100
output 
1+99=100
input 
123123123456456456579579579
output 
123123123+456456456=579579579