#include <algorithm>
#include <any>
#include <array>
#include <assert.h>
#include <atomic>
#include <bit>
#include <bits/stdc++.h>
#include <bitset>
#include <cassert>
#include <ccomplex>
#include <cctype>
#include <cerrno>
#include <cfenv>
#include <cfloat>
#include <charconv>
#include <chrono>
#include <cinttypes>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <codecvt>
#include <complex.h>
#include <complex>
#include <condition_variable>
#include <csetjmp>
#include <csignal>
#include <cstdalign>
#include <cstdarg>
#include <cstdbool>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctgmath>
#include <ctime>
#include <ctype.h>
#include <cuchar>
#include <cwchar>
#include <cwctype>
#include <cxxabi.h>
#include <deque>
#include <errno.h>
#include <exception>
#include <execution>
#include <fenv.h>
#include <filesystem>
#include <float.h>
#include <forward_list>
#include <fstream>
#include <functional>
#include <future>
#include <initializer_list>
#include <inttypes.h>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits.h>
#include <limits>
#include <list>
#include <locale.h>
#include <locale>
#include <map>
#include <math.h>
#include <memory>
#include <memory_resource>
#include <mutex>
#include <new>
#include <numeric>
#include <optional>
#include <ostream>
#include <queue>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <set>
#include <setjmp.h>
#include <shared_mutex>
#include <signal.h>
#include <sstream>
#include <stack>
#include <stdarg.h>
#include <stddef.h>
#include <stdexcept>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <streambuf>
#include <string.h>
#include <string>
#include <string_view>
#include <strstream>
#include <system_error>
#include <tgmath.h>
#include <thread>
#include <time.h>
#include <tuple>
#include <type_traits>
#include <typeindex>
#include <typeinfo>
#include <uchar.h>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <valarray>
#include <variant>
#include <vector>
#include <version>
#include <wchar.h>
#include <wctype.h>

using namespace std;
class tool {
    string turn_left(string a, int h) {
        for (int i = 1; i <= h; i++) {
            a = "0" + a;
        }
        return a;
    }
    string turn_right(string a, int h) {
        for (int i = 1; i <= h; i++) {
            a = a + "0";
        }
        return a;
    }
    string abs(string a) {
        if (a.find('-') != a.npos) {
            a.erase(0, 1);
            return a;
        } else {
            return a;
        }
    }
    string maxx(string a, string b) {
        for (int i = a.size() - 1; i >= 0; i--) {
            if (a[i] == '0') {
                a.erase(i, 1);
            } else {
                break;
            }
        }
        if (a[a.size() - 1] == '.') {
            a.erase(a.size() - 1, 1);
        }
        for (int i = b.size() - 1; i >= 0; i--) {
            if (b[i] == '0') {
                b.erase(i, 1);
            } else {
                break;
            }
        }
        if (b[b.size() - 1] == '.') {
            b.erase(b.size() - 1, 1);
        }
        if (a.find('.') == a.npos && b.find('.') == b.npos) {
            if (a.size() > b.size()) {
                return a;
            } else if (a.size() < b.size()) {
                return b;
            } else {
                if (a > b) {
                    return a;
                } else {
                    return b;
                }
            }
        } else {
            if (a.find('.') == a.npos) {
                a = a + ".0";
            }
            if (b.find('.') == b.npos) {
                b = b + ".0";
            }
            if (a.find('.') > b.find('.')) {
                return a;
            } else if (a.find('.') < b.find('.')) {
                return b;
            } else {
                if (a.size() > b.size()) {
                    return a;
                } else if (b.size() > a.size()) {
                    return b;
                } else {
                    for (int i = 0; i < a.size(); i++) {
                        if (a[i] > b[i]) {
                            return a;
                        }
                        if (b[i] > a[i]) {
                            return b;
                        }
                    }
                    return a;
                }
            }
        }
    }
    string plus(string a, string b) {
        if (a.find('.') == a.npos) {
            a = a + ".0";
        }
        if (b.find('.') == b.npos) {
            b = b + ".0";
        }
        a = turn_left(a, max(a.find('.'), b.find('.')) - a.find('.'));
        b = turn_left(b, max(a.find('.'), b.find('.')) - b.find('.'));
        a = turn_right(a,
                       max((a.size() - a.find('.')), (a.size() - a.find('.'))));
        b = turn_right(b,
                       max((a.size() - a.find('.')), (b.size() - b.find('.'))));
        string c = "";
        for (int i = 0; i < a.size(); i++) {
            if (a[i] != '.') {
                c = c + '0';
            } else {
                c = c + '.';
            }
        }
        for (int i = a.size(); i >= 0; i--) {
            if (a[i] == '.') {
                continue;
            }
            int z = int(a[i] - '0') + int(b[i] - '0') + int(c[i] - '0');
            c[i] = char(z % 10 + '0');
            if (z >= 10) {
                if (i == 0) {
                    c = char(z / 10 + '0') + c;
                } else {
                    if (c[i - 1] != '.') {
                        c[i - 1] = char(z / 10 + '0');
                    } else {
                        c[i - 2] = char(z / 10 + '0');
                    }
                }
            }
        }
        for (int i = c.size() - 1; i >= 0; i--) {
            if (c[i] == '0') {
                c.erase(i, 1);
            } else {
                break;
            }
        }
        if (c[c.size() - 1] == '.') {
            c.erase(c.size() - 1, 1);
        }
        return c;
    }
    string recude(string a, string b) {
        string c = "";
        bool negative = false;
        if (a == b) {
            return "0";
        }
        for (int i = 1; i <= (a.size() - b.size()); i++) {
            b = '0' + b;
        }
        for (int i = 1; i <= a.size(); i++) {
            c = c + '0';
        }
        for (int i = 0; i <= a.size() - 1; i++) {
            int s = int(a[i] - '0') - int(b[i] - '0');
            if (s >= 0) {
                c[i] = char(s + '0');
            } else {
                int be = 1;
                while (c[i - be] == 0) {
                    c[i - be] = '9';
                    be++;
                }
                c[i - be]--;
                c[i] = char((10 + s) + '0');
            }
        }
        for (int i = 0; i < c.size(); i++) {
            if (c[i] == '0') {
                c.erase(0, 1);
            } else {
                break;
            }
        }
        return c;
    }
    string time2_1(string a, char b) {
        string c = "";
        a = '0' + a;
        int be = 1;
        for (int i = 1; i <= a.size(); i++) {
            c = c + '0';
        }
        for (int i = a.size() - 1; i > 0; i--) {
            int s = int(a[i] - '0');
            int p = int(b - '0');
            int v = int(c[i] - '0');
            int ans = s * p + v;
            c[i] = char(ans % 10 + '0');
            int plus = ans / 10;
            while (int(c[i - be] - '0') + plus >= 10) {
                c[i - be] = char((int(c[i - be]) + plus) % 10 + '0');
                plus = (int(c[i - be]) + plus) / 10;
                be++;
            }
            c[i - be] = char((int(c[i - be] - '0') + plus) % 10 + '0');
            be = 1;
        }
        if (c[0] == '0') {
            c.erase(0, 1);
        }
        return c;
    }
    string time(string a, string b) {
        string c = "0";
        for (int i = b.size() - 1; i >= 0; i--) {
            string s = time2_1(a, b[i]);
            for (int j = 1; j <= (b.size() - i - 1); j++) {
                s = s + '0';
            }
            c = plus(c, s);
        }
        return c;
    }
    inline long long int read() {
        register long long int s = 0;
        register char ch = getchar();
        register long long int a = 1;
        while (ch < '0' || ch > '9') {
            if (ch == '-') {
                a = -1;
            }
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            s = s * 10 + ch - '0';
            ch = getchar();
        }
        return s * a;
    }
    inline void write(long long int a) {
        if (a < 0) {
            putchar('-');
            a = -a;
        }
        if (a > 9) {
            write(a / 10);
        }
        putchar(a % 10 + '0');
    }
    long long int pow_low_0(long long int a, long long int b) {
        long long int ans = 1;
        long long int minn = min(a, b);
        long long int maxn = max(a, b);
        for (long long int i = 1; i <= minn; i++) {
            ans = ans * minn;
        }
        return ans;
    }
    long long int pow_low_1(long long int a, long long int b) {
        long long int r = 1;
        while (b--) {
            r *= a;
        }
        return r;
    }
    long long int pow_low_2(long long int a, long long int b) {
        long long int r = 1, base = a;
        while (b != 0) {
            if (b % 2) {
                r *= base;
            }
            base *= base;
            b /= 2;
        }
        return r;
    }
    long long pow_low_3(long long int x, long long int n) {
        if (n == 0) {
            return 1;
        }
        long long int t = 1;
        while (n != 0) {
            if (n & 1)
                t *= x;
            n >>= 1;
            x *= x;
        }
        return t;
    }
    void Qsort(int arr[], int low, int high) {
        if (high <= low)
            return;
        int i = low;
        int j = high;
        int key = arr[low];
        while (true) {
            while (arr[i] <= key) {
                i++;
                if (i == high) {
                    break;
                }
            }
            while (arr[j] >= key) {
                j--;
                if (j == low) {
                    break;
                }
            }
            if (i >= j)
                break;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        arr[low] = arr[j];
        arr[j] = key;
        Qsort(arr, low, j - 1);
        Qsort(arr, j + 1, high);
    }
    void Ss(int arr[], int begin, int end) {
        for (int i = begin; i <= end; i++) {
            int min = i;
            for (int j = i + 1; j <= end; j++) {
                if (arr[min] > arr[j]) {
                    min = j;
                }
            }
            if (min != i) {
                int tmp = arr[i];
                arr[i] = arr[min];
                arr[min] = tmp;
            }
        }
        return;
    }
    void Is(int arr[], int begin, int end) {
        if (end - begin == 0) {
            return;
        }
        for (int i = begin; i <= end; i++) {
            int j = i;
            while (j > 0) {
                if (arr[j - 1] > arr[j]) {
                    swap(arr[j], arr[j - 1]);
                }
                j--;
            }
        }
        return;
    }
    void SHs(int arr[], int lengh) {
        for (int gap = lengh / 2; gap > 0; gap = gap / 2) {
            for (int i = gap; i < lengh; i++) {
                int j = i;
                while ((j - gap) >= 0 && arr[j] < arr[j - gap]) {
                    swap(arr[j], arr[j - gap]);
                    j = j - gap;
                }
            }
        }
        return;
    }
    void Ms_low(int arr[], int left, int mid, int right) {
        int curleft = left;
        int curmid = mid;
        int len = right - left + 1;
        int *tmp = new int[len];
        int *cur = tmp;
        while (curleft < mid && curmid <= right) {
            if (arr[curleft] <= arr[curmid]) {
                *cur++ = arr[curleft++];
            } else {
                *cur++ = arr[curmid++];
            }
        }
        while (curleft < mid) {
            *cur++ = arr[curleft++];
        }
        while (curmid <= right) {
            *cur++ = arr[curmid++];
        }
        for (int i = left, k = 0; i <= right;) {
            arr[i++] = tmp[k++];
        }
        delete[] tmp;
    }
    void Ms(int arr[], int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) >> 1;
        Ms(arr, left, mid);
        Ms(arr, mid + 1, right);
        Ms_low(arr, left, mid + 1, right);
    }
    void Hs_low(int arr[], int lengh, int root) {
        int left_child = root * 2 + 1;
        int right_child = root * 2 + 2;
        int max_idx = root;
        if (left_child < lengh && arr[left_child] > arr[max_idx]) {
            max_idx = left_child;
        }
        if (right_child < lengh && arr[right_child] > arr[max_idx]) {
            max_idx = right_child;
        }
        if (max_idx != root) {
            swap(arr[max_idx], arr[root]);
            Hs_low(arr, lengh, max_idx);
        }
    }
    void Hs(int arr[], int lengh) {
        for (int i = lengh / 2 - 1; i >= 0; i--) {
            Hs_low(arr, lengh, i);
        }
        for (int i = lengh - 1; i > 0; i--) {
            swap(arr[0], arr[i]);
            Hs_low(arr, i, 0);
        }
    }
    void Cs(int arr[], int lengh, int max_value) {
        if (arr == NULL || lengh <= 0) {
            return;
        }
        int *tmp = new int[max_value + 1]();
        for (int i = 0; i < lengh; i++) {
            ++tmp[arr[i]];
        }
        int idx = 0;
        for (int i = 0; i < max_value; i++) {
            while (tmp[i] > 0) {
                arr[idx++] = i;
                --tmp[i];
            }
        }
        return;
    }
    void Bs(int arr[], int len) {
        if (len <= 0) {
            return;
        }
        int i;
        int j;
        int **buckets = new int *[10];
        for (int i = 0; i < 10; i++) {
            buckets[i] = new int[100];
        }
        int count[10] = {0};
        for (int i = 0; i < len; i++) {
            int temp = arr[i];
            int index = temp / 10;
            buckets[index][count[index]] = temp;
            int j = count[index]++;
            for (; j > 0 && temp < buckets[index][j - 1]; j--) {
                buckets[index][j] = buckets[index][j - 1];
            }
            buckets[index][j] = temp;
        }
        int k = 0;
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < count[i]; j++) {
                arr[k++] = buckets[i][j];
            }
        }
        for (int i = 0; i < 10; i++) {
            delete[] buckets[i];
            buckets[i] = NULL;
        }
        delete[] buckets;
        buckets = NULL;
        return;
    }
    int CAs_low(int arr[], int len) {
        if (len <= 0) {
            return 0;
        }
        int ret = 0;
        for (int i = 0; i < len; i++) {
            int tmp = arr[i];
            int k = 0;
            while (tmp > 0) {
                tmp /= 10;
                k++;
            }
            if (k > ret) {
                ret = k;
            }
        }
        return ret;
    }
    void Rs(int arr[], int len) {
        if (len <= 0) {
            return;
        }
        int max_bits = CAs_low(arr, len);
        int *count = new int[10];
        int *tmp = new int[len];
        int redix = 1;
        for (int i = 0; i < max_bits; i++) {
            for (int t = 0; t < 10; t++) {
                count[t] = 0;
            }
            for (int j = 0; j < len; j++) {
                int tmpp = (arr[j] / redix) % 10;
                count[tmpp]++;
            }
            for (int j = 1; j < 10; j++) {
                count[j] += count[j - 1];
            }
            for (int j = len - 1; j >= 0; j--) {
                int tmpp = (arr[j] / redix) % 10;
                tmp[count[tmpp] - 1] = arr[j];
                count[tmpp];
            }
            for (int j = 0; j < len; j++) {
                arr[j] = tmp[j];
            }
            redix *= 10;
        }
        delete[] tmp;
        delete[] count;
        return;
    }
};