Problem 863A : Insert Digit || Full Detailed Solution || Codeforces

 Question :

You have a positive number of length n and one additional digit.

You can insert this digit anywhere in the number, including at the beginning or at the end.

Your task is to make the result as large as possible.

For example, you have the number 76543$76543$, and the additional digit is 4$4$. Then the maximum number you can get is 765443$765443$, and it can be obtained in two ways — by inserting a digit after the 3$3$th or after the 4$4$th digit of the number.

Input

The first line contains a single integer t  (1≤t≤104) — the number of test cases.The descriptions of the test cases follow.

The first line of the description of each test case contains two integers n$�$ and d$�$ (1≤n≤2⋅105$1\le �\le 2\cdot {10}^5$; 0≤d≤9$0\le �\le 9$) — the length of the number and an additional digit, respectively.

The second line of the description of each test case contains a string consisting of n$�$ digits — the number that you have initially. It is guaranteed that the number does not contain leading zeros.

It is guaranteed that the sum of  nn for all test cases does not exceed 2⋅105$\mathrm{.}$

Output

For each test case, output a string consisting of n+1$\mathrm{<br>}$ digits — the maximum possible number that can be obtained.

Example

input

Copy

11
5 4
76543
1 0
1
2 5
44
3 6
666
5 6
13579
5 8
97531
19 4
9876543210123456789
5 7
73737
8 1
20000000
7 0
7058959
12 1
828127127732

output

Copy

765443
10
544
6666
613579
987531
98765443210123456789
773737
210000000
70589590
8281271277321

Explanation :

Find the first digit less than d and insert d before it. If there's no such digit, insert at the end.

SOLUTION :

/* Deepak Yadav */

#pragma GCC optimize("O3,unroll-loops")

#include<bits/stdc++.h>

#include<ext/pb_ds/assoc_container.hpp>

#include<ext/pb_ds/tree_policy.hpp>

using namespace std;

using namespace chrono;

using namespace __gnu_pbds;

#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

#define MOD 1000000007

#define MOD1 998244353

#define INF 1e18

#define nline "\n"

#define pb push_back

#define ppb pop_back

#define mp make_pair

#define ff first

#define ss second

#define PI 3.141592653589793238462

#define set_bits(x) __builtin_popcountll(x)

#define sz(x) ((int)(x).size())

#define all(x) (x).begin(), (x).end()

#define test     long long T;cin>>T;while(T--)

//#define ll             long long

#define fl(x, n) for (int x = 0; x < n; ++x)

#define cina(a, n) for(int i=0;i<n;i++){cin>>a[i];}

#ifdef Priyansh31dec

#define debug(x) cerr << #x<<" "; _print(x); cerr << endl;

#else

#define debug(x);

#endif

typedef long long ll;

typedef unsigned long long ull;

typedef long double lld;

typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update > pbds; // find_by_order, order_of_key

void _print(ll t) {cerr << t;}

void _print(int t) {cerr << t;}

void _print(string t) {cerr << t;}

void _print(char t) {cerr << t;}

void _print(lld t) {cerr << t;}

void _print(double t) {cerr << t;}

void _print(ull t) {cerr << t;}

bool Campare(const auto a, const auto b){

     if(a.first==b.first) return a.second<b.second;

     return a.first>b.first;

}

bool prime[1000001];

#define int    long long int

int divisor(int n){

  int cnt=0;

  for(int i=1;i<=n;i++){

     if(n%i==0) cnt++;

  }

  return cnt;

}

void solve(){

    //1811A

    int n; char d; cin>>n>>d;

    string s; cin>>s;

    string ans = "";

    int flag=1;

    for(int i=0;i<n;i++){

        if(s[i]>=d) {ans += s[i];}

        else if(flag==1) {ans += d; flag=0; i-- ;}

        else ans += s[i];

    }

    if(flag) ans += d;

    cout<<ans<<endl;

}

signed main() {

#ifdef deepakyadav123

    freopen("Error.txt", "w", stderr);

#endif

    fastio();

    auto start1 = high_resolution_clock::now();

    test

    solve();

    auto stop1 = high_resolution_clock::now();

    auto duration = duration_cast<microseconds>(stop1 - start1);

#ifdef deepakyadav123

    cerr << "Time: " << duration . count() / 1000 << endl;

#endif

}

I Hope you liked it please tell me the suggestion in the comment below what shoud I change according to you.

And discuss the Approach in comment section if you want. share the solution with you frnds too.