题干：

Petya loves lucky numbers. Everybody knows that lucky numbers are positive integers whose decimal representation contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Petya has a number consisting of n digits without leading zeroes. He represented it as an array of digits without leading zeroes. Let's call it d. The numeration starts with 1, starting from the most significant digit. Petya wants to perform the following operation k times: find the minimum x (1 ≤ x < n) such that dx = 4 and dx + 1 = 7, if x is odd, then to assign dx = dx + 1 = 4, otherwise to assign dx = dx + 1 = 7. Note that if no x was found, then the operation counts as completed and the array doesn't change at all.

You are given the initial number as an array of digits and the number k. Help Petya find the result of completing k operations.

Input

The first line contains two integers n and k (1 ≤ n ≤ 105, 0 ≤ k ≤ 109) — the number of digits in the number and the number of completed operations. The second line contains n digits without spaces representing the array of digits d, starting with d1. It is guaranteed that the first digit of the number does not equal zero.

Output

In the single line print the result without spaces — the number after the koperations are fulfilled.

Examples

Input

7 4
4727447

Output

4427477

Input

4 2
4478

Output

4478

Note

In the first sample the number changes in the following sequence: 4727447 → 4427447 → 4427477 → 4427447 → 4427477.

In the second sample: 4478 → 4778 → 4478.

题目大意：

    给定一个字符串，每次从左到右找第一个 47 ，然后判断其起始下标是偶数还是奇数，若为奇数，则替换为 44 ，否则替换为 77 ，最多操作 k 次，求最终结果。

解题报告：

  这题需要注意的是数据范围。 显然我们把 47 替换为 44 只会对当前位置以后产生影响，而替换为 77 则会对当前位置以前产生影响。若串中 i−1 i-1 的位置也为 4 ，则会发现 447 这部分会产生循环，此时可以直接得出结果，否则遍历一下原串照题意修改即可。

  值得注意的是，刚开始写的时候TLE了，是循环了多次，后来发现是不需要这样的，直接遍历一遍数组顺便更改字符串就好，主要还是因为那句：只有替换为77，才可能对以前的位置产生影响，否则的话都是直接遍历一遍就好了，不需要每次都从头找。

  还有一个要注意的地方，我是用string读的字符串，所以奇偶正好和题干叙述相反才对。

AC代码：

#include<string>
#include<iostream>
#define ll long long
using namespace std;
const int MAX = 1e5 +5;
int k,n;
int main()
{
	string s;
	cin>>n >> k;
	cin>>s;
	int len = s.length();
	int flag = 0;
	for(int i = 0; i<len-1 && k; i++) {
		if(s[i] == '4' && s[i+1] == '7') {
			if(i>=1 && s[i-1] == '4') {
				if(i%2==1) {
					if(k%2==1) {
						s[i] = '7';
					}
					k-=k,flag=1;continue;
				}
			}
			if(i%2==0) s[i+1]='4';
			else s[i]='7';
			flag=1;
			k--;
		}
	}
	cout << s << endl;
	return 0 ;
 }

1TLE：原因在于程序就写的和初心不符。那句本来就该放到这个if外面的。

#include<string>
#include<iostream>
#define ll long long
using namespace std;
const int MAX = 1e5 +5;
int k,n;
int main()
{
	string s;
	cin>>n >> k;
	cin>>s;
	
	int len = s.length();
	while(k>0) {
		int flag = 0;
		for(int i = 0; i<len-1; i++) {
			if(s[i] == '4' && s[i+1] == '7') {
				if(i>=1 && s[i-1] == '4') {
					if(i%2==1) {
						if(k%2==1) {
							s[i] = '7',k-=k,flag=1;break;//k-=k,flag=1;break;这三句应该放到这个if的外面
						}
					}
				}
				if(i%2==0) s[i+1]='4';
				else s[i]='7';	
				flag=1;
				k--;
				break;
			}
		}
		if(flag == 0) break;
	}
	cout << s << endl;
	return 0 ;
 }

2TLE：这次就真的是因为思路的原因TLE了，考虑到了   扫到447时可以直接出结果，但是还是有数据可以卡到O(nk)的复杂度，所以肯定还是说不过去的。

#include<string>
#include<iostream>
#define ll long long
using namespace std;
const int MAX = 1e5 +5;
int k,n;
int main()
{
	string s;
	cin>>n >> k;
	cin>>s;
	
	int len = s.length();
	while(k>0) {
		int flag = 0;
		for(int i = 0; i<len-1; i++) {
			if(s[i] == '4' && s[i+1] == '7') {
				if(i>=1 && s[i-1] == '4') {
					if(i%2==1) {
						if(k%2==1) {
							s[i] = '7';
						}
						k-=k,flag=1;break;
					}
				}
				if(i%2==0) s[i+1]='4';
				else s[i]='7';	
				flag=1;
				k--;
				break;
			}
		}
		if(flag == 0) break;
	}
	cout << s << endl;
	return 0 ;
 }

3WA：（由TLE到WA、、、Orz）其实这次原因也很简单，就是直接在上面那个程序上改的，所以break直接去掉了，改成ifelse了。。其实不应该这样的，应该continue才对。因为对于这个代码3，如果一个样例是4447，循环到44‘4’7的时候，进入了1，但是没进入2，本意是跳到3执行，但是这样的话就没执行3，而是直接i++到下一个for中了。

#include<string>
#include<iostream>
#define ll long long
using namespace std;
const int MAX = 1e5 +5;
int k,n;
int main()
{
	string s;
	cin>>n >> k;
	cin>>s;

	int len = s.length();
//	while(k>0) {
		int flag = 0;
		for(int i = 0; i<len-1 && k; i++) {
			if(s[i] == '4' && s[i+1] == '7') {
				if(i>=1 && s[i-1] == '4') {    //1
					if(i%2==1) {                //2
						if(k%2==1) {
							s[i] = '7';
						}
						k-=k,flag=1;
					}
				}
				else {                            //3
					if(i%2==0) s[i+1]='4';
					else s[i]='7';
					flag=1;
					k--;
				}
			}
		}
//	}
	cout << s << endl;
	return 0 ;
 }

总结：  还是要注意if的层次啊！是并列？还是包含关系？再看一遍这题！