Algorithm

B. Lucky Transformation
time limit per test
2 seconds
memory limit per test
256 megabytes
Problem Link- https://codeforces.com/problemset/problem/121/B
input
standard input
output
standard output

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 k operations are fulfilled.

Examples
input
Copy
7 4
4727447
output
Copy
4427477
input
Copy
4 2
4478
output
Copy
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.



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <iostream>

int main(){

    long n,k; std::cin >> n >> k;
    std::string s; std::cin >> s;

    for(int p = 0; p < s.length() && k; p++){
      if(s[p] == '4' && s[p + 1] == '7'){
        if(p % 2 == 0){s[p] = s[p + 1] = '4';}
        else if(s[p - 1] == '4'){if(k % 2 == 0){s[p]='4';} else{s[p] = '7';} break;}
        else{s[p] = s[p+1] = '7';}
        k--;
      }
    }

    std::cout << s << std::endl;

    return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
7 4
4727447

Output

x
–
+
cmd
4427477
Advertisements

Demonstration

Codeforces Solution-B. Lucky Transformation-Solution in C, C++, Java, Python

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+