कहाँ Yandex उम्मीदवारों के लिए वास्तविक समस्याओं को हल करने के लिए: Codeforces और विश्लेषण पर प्रशिक्षण

import collections
import math
import typing
from decimal import Decimal


class Amount(object):
    def __init__(self, count: Decimal, unit: str):
        self.count = count
        self.unit = unit

    def convert_to(self, unit: str):
        multipliers_dict = {
            'g': 1,
            'kg': 1000,
            'ml': 1,
            'l': 1000,
            'cnt': 1,
            'tens': 10
        }
        assert self.is_compatible(self.unit, unit)

        return Amount(self.count * multipliers_dict[self.unit] / multipliers_dict[unit], unit)

    @staticmethod
    def is_compatible(unit1, unit2):
        unit_classes = [
            ('g', 'kg'),
            ('ml', 'l'),
            ('cnt', 'tens')
        ]

        for unit_class in unit_classes:
            if unit1 in unit_class:
                return unit2 in unit_class
        return False


class FoodInfo(object):
    def __init__(self, proteins: Decimal = Decimal(0), fats: Decimal = Decimal(0), carbohydrates: Decimal = Decimal(0), food_value: Decimal = Decimal(0)):
        self.proteins = proteins
        self.fats = fats
        self.carbohydrates = carbohydrates
        self.food_value = food_value

    def __mul__(self, other: Decimal):
        assert isinstance(other, Decimal)

        return FoodInfo(self.proteins * other, self.fats * other, self.carbohydrates * other, self.food_value * other)

    def __add__(self, other):
        assert isinstance(other, FoodInfo)

        return FoodInfo(
            self.proteins + other.proteins,
            self.fats + other.fats,
            self.carbohydrates + other.carbohydrates,
            self.food_value + other.food_value
        )


class AmountFoodInfo(object):
    def __init__(self, amount, food_info):
        self.amount = amount
        self.food_info = food_info


class Ingredient(object):
    def __init__(self, name: str, amount: Amount):
        self.name = name
        self.amount = amount


class CatalogIngredientInfo(object):
    def __init__(self, name: str, price: int, amount: Amount):
        self.name = name
        self.price = price
        self.amount = amount


class Dish(object):
    def __init__(self, name: str, count: int, ingredients: typing.List[Ingredient]):
        self.name = name
        self.count = count
        self.ingredients = ingredients


def read_dishes():
    dish_count = int(input())

    dishes = []
    for _ in range(dish_count):
        dish_name, dish_count, ingredient_count = input().split(' ')
        ingredient_count = int(ingredient_count)

        ingredients = []
        for _ in range(ingredient_count):
            ingredient_name, amount, unit = input().split(' ')
            ingredients.append(Ingredient(name=ingredient_name, amount=Amount(Decimal(amount), unit)))

        dishes.append(Dish(name=dish_name, ingredients=ingredients, count=int(dish_count)))

    return dishes


def read_catalog():
    ingredient_count = int(input())

    catalog = {}
    for _ in range(ingredient_count):
        name, price, amount, unit = input().split(' ')
        catalog[name] = CatalogIngredientInfo(
            name=name,
            price=int(price),
            amount=Amount(Decimal(amount), unit)
        )

    return catalog


def read_food_info():
    info_count = int(input())

    food_info = {}
    for _ in range(info_count):
        name, amount, unit, proteins, fats, carbohydrates, food_value = input().split(' ')
        food_info[name] = AmountFoodInfo(
            amount=Amount(
                count=Decimal(amount),
                unit=unit
            ),
            food_info=FoodInfo(
                proteins=Decimal(proteins),
                fats=Decimal(fats),
                carbohydrates=Decimal(carbohydrates),
                food_value=Decimal(food_value)
            )
        )

    return food_info


def main():
    dishes = read_dishes()
    catalog = read_catalog()
    food_info = read_food_info()

    need_ingredients = collections.defaultdict(Decimal)
    need_ingredients_count = collections.defaultdict(int)
    dish_info = collections.defaultdict(FoodInfo)
    for dish in dishes:
        for ingredient in dish.ingredients:
            converted_amount = ingredient.amount.convert_to(catalog[ingredient.name].amount.unit)
            converted_food_info_amount = food_info[ingredient.name].amount.convert_to(catalog[ingredient.name].amount.unit)
            need_ingredients[ingredient.name] += converted_amount.count * dish.count
            dish_info[dish.name] += food_info[ingredient.name].food_info * (converted_amount.count / converted_food_info_amount.count)

    total_price = Decimal(0)
    for ingredient_name, need_ingredient in need_ingredients.items():
        need_count = need_ingredient // catalog[ingredient_name].amount.count
        if need_count * catalog[ingredient_name].amount.count < need_ingredient:
            need_count += 1

        need_ingredients_count[ingredient_name] = need_count
        total_price += catalog[ingredient_name].price * need_count

    print(total_price)
    for name in catalog.keys():
        print(name, need_ingredients_count[name])

    for name, info in dish_info.items():
        print(name, info.proteins, info.fats, info.carbohydrates, info.food_value)


if __name__ == '__main__':
    main()

#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <assert.h>
#include <algorithm>
#include <iomanip>
#include <time.h>
#include <math.h>
#include <bitset>
#include <unordered_map>

#pragma comment(linker, "/STACK:256000000")

using namespace std;

typedef long long int ll;
typedef long double ld;

const int INF = 1000 * 1000 * 1000 + 21;
const ll LLINF = (1ll << 60) + 5;
const int MOD = 1000 * 1000 * 1000 + 7;

const int MAX_N = 10 * 1000 + 227;
const int MAX_LEN = 35;

struct ig_info {
    ll cost = 0;
    ll cnt = 0;
    ll buy_cnt = 0;
    ll eg_cnt = 0;
    ld arr[4] = {0.0, 0.0, 0.0, 0.0};
};

struct rs {
    string name;
    ll mult = 0;
    vector<pair<string, ll>> igs;
    ld arr[4] = {0.0, 0.0, 0.0, 0.0};
};

int n, k, m;
char buf[MAX_LEN];
char buf_cnt[MAX_LEN];
rs arr[MAX_N];
unordered_map<string, ig_info> info;

ll get_cnt() {
    ll cnt;
    scanf("%lld %s", &cnt, buf_cnt);
    if (!strcmp(buf_cnt, "kg") || !strcmp(buf_cnt, "l")) {
        return 1000 * cnt;
    }
    if (!strcmp(buf_cnt, "tens")) {
        return 10 * cnt;
    }
    return cnt;
}

int main() {
#ifdef CH_EGOR
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#else
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
#endif

    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        int sz;
        scanf("%s%lld%d", buf, &arr[i].mult, &sz);
        arr[i].name = buf;
        arr[i].igs.resize(sz);
        for (int j = 0; j < sz; ++j) {
            scanf("%s", buf);
            arr[i].igs[j].first = buf;
            arr[i].igs[j].second = get_cnt();
        }
    }

    scanf("%d", &k);
    for (int i = 0; i < k; ++i) {
        ll cost;
        scanf("%s%lld", buf, &cost);
        ig_info& cur_info = info[buf];
        cur_info.cost = cost;
        cur_info.cnt = get_cnt();
    }

    scanf("%d", &m);
    for (int i = 0; i < m; ++i) {
        scanf("%s", buf);
        ig_info& cur_info = info[buf];
        cur_info.eg_cnt = get_cnt();
        for (int j = 0; j < 4; ++j) {
            double x;
            scanf("%lf", &x);
            cur_info.arr[j] = x;
        }
        if (cur_info.cnt == 0) {
            info.erase(buf);
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < (int)arr[i].igs.size(); ++j) {
            ig_info& cur_info = info[arr[i].igs[j].first];
            cur_info.buy_cnt += arr[i].mult * arr[i].igs[j].second;
            for (int k = 0; k < 4; ++k) {
                arr[i].arr[k] += ((double)arr[i].igs[j].second / (double)cur_info.eg_cnt) * cur_info.arr[k];
            }
        }
    }

    ll ans = 0;
    for (auto& cur_info : info) {
        cur_info.second.buy_cnt = (cur_info.second.buy_cnt + cur_info.second.cnt - 1) / cur_info.second.cnt;
        ans += cur_info.second.buy_cnt * cur_info.second.cost;
    }

    printf("%lld\n", ans);

    for (const auto& cur_info : info) {
        printf("%s %lld\n", cur_info.first.c_str(), cur_info.second.buy_cnt);
    }

    for (int i = 0; i < n; ++i) {
        printf("%s ", arr[i].name.c_str());
        for (int j = 0; j < 4; ++j) {
            printf("%.20lf%c", (double)arr[i].arr[j], " \n"[j == 3]);
        }
    }

    return 0;
}

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.util.HashMap;
import java.io.IOException;
import java.util.Map.Entry;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author ch_egor
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        Recipes solver = new Recipes();
        solver.solve(1, in, out);
        out.close();
    }

    static class Recipes {
        static final int CNT_ENERGY = 4;

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.nextInt();

            Recipes.Recipe[] recipes = new Recipes.Recipe[n];
            for (int i = 0; i < n; ++i) {
                recipes[i] = new Recipes.Recipe();
                recipes[i].name = in.nextString();
                recipes[i].mult = in.nextLong();

                int ingredientsSize = in.nextInt();
                recipes[i].ingredients = new Recipes.Ingredient[ingredientsSize];
                for (int j = 0; j < recipes[i].ingredients.length; ++j) {
                    recipes[i].ingredients[j] = new Recipes.Ingredient();
                    recipes[i].ingredients[j].name = in.nextString();
                    recipes[i].ingredients[j].cnt = readCnt(in);
                }
            }

            int k = in.nextInt();
            HashMap<String, Recipes.IngredientBuyInfo> ingredientBuyInfo = new HashMap<>();
            for (int i = 0; i < k; ++i) {
                String name = in.nextString();

                Recipes.IngredientBuyInfo curBuyInfo = new Recipes.IngredientBuyInfo();
                curBuyInfo.cost = in.nextLong();
                curBuyInfo.cnt = readCnt(in);

                ingredientBuyInfo.put(name, curBuyInfo);
            }

            int m = in.nextInt();
            HashMap<String, Recipes.IngredientEnergyInfo> ingredientEnergyInfo = new HashMap<>();
            for (int i = 0; i < m; ++i) {
                String name = in.nextString();

                Recipes.IngredientEnergyInfo curEnergyInfo = new Recipes.IngredientEnergyInfo();
                curEnergyInfo.cnt = readCnt(in);
                for (int j = 0; j < CNT_ENERGY; ++j) {
                    curEnergyInfo.energyArr[j] = in.nextDouble();
                }

                ingredientEnergyInfo.put(name, curEnergyInfo);
            }

            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < recipes[i].ingredients.length; ++j) {
                    Recipes.IngredientBuyInfo curBuyInfo = ingredientBuyInfo.get(recipes[i].ingredients[j].name);
                    curBuyInfo.buyCnt += recipes[i].mult * recipes[i].ingredients[j].cnt;

                    Recipes.IngredientEnergyInfo curEnergyInfo = ingredientEnergyInfo.get(recipes[i].ingredients[j].name);
                    for (int p = 0; p < CNT_ENERGY; ++p) {
                        recipes[i].energyArr[p] += ((double) recipes[i].ingredients[j].cnt / (double) curEnergyInfo.cnt) * curEnergyInfo.energyArr[p];
                    }
                }
            }

            long totalCost = 0;
            for (HashMap.Entry<String, Recipes.IngredientBuyInfo> entry : ingredientBuyInfo.entrySet()) {
                totalCost += entry.getValue().cost * ((entry.getValue().buyCnt + entry.getValue().cnt - 1) / entry.getValue().cnt);
            }

            out.println(totalCost);

            for (HashMap.Entry<String, Recipes.IngredientBuyInfo> entry : ingredientBuyInfo.entrySet()) {
                out.println(entry.getKey() + " " + ((entry.getValue().buyCnt + entry.getValue().cnt - 1) / entry.getValue().cnt));
            }

            for (int i = 0; i < n; ++i) {
                out.print(recipes[i].name + " ");
                for (int j = 0; j < CNT_ENERGY; ++j) {
                    out.print(String.format("%.20f", recipes[i].energyArr[j]) + (j == CNT_ENERGY - 1 ? "\n" : " "));
                }
            }
        }

        private long readCnt(InputReader in) {
            int cnt = in.nextInt();
            String type = in.nextString();
            if (type.compareTo("kg") == 0 || type.compareTo("l") == 0) {
                return 1000 * cnt;
            }
            if (type.compareTo("tens") == 0) {
                return 10 * cnt;
            }
            return cnt;
        }

        static class Ingredient {
            String name;
            long cnt;

        }

        static class IngredientBuyInfo {
            long cost;
            long cnt;
            long buyCnt;

        }

        static class IngredientEnergyInfo {
            long cnt;
            double[] energyArr;

            IngredientEnergyInfo() {
                energyArr = new double[CNT_ENERGY];
                for (int i = 0; i < CNT_ENERGY; ++i) {
                    energyArr[i] = 0.0;
                }
            }

        }

        static class Recipe {
            String name;
            long mult;
            Recipes.Ingredient[] ingredients;
            double[] energyArr;

            Recipe() {
                energyArr = new double[CNT_ENERGY];
                for (int i = 0; i < CNT_ENERGY; ++i) {
                    energyArr[i] = 0.0;
                }
            }

        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new UnknownError();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new UnknownError();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new UnknownError();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new UnknownError();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public String nextString() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                if (Character.isValidCodePoint(c)) {
                    res.appendCodePoint(c);
                }
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public double nextDouble() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            double res = 0;
            while (!isSpaceChar(c) && c != '.') {
                if (c == 'e' || c == 'E') {
                    return res * Math.pow(10, nextInt());
                }
                if (c < '0' || c > '9') {
                    throw new UnknownError();
                }
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '.') {
                c = read();
                double m = 1;
                while (!isSpaceChar(c)) {
                    if (c == 'e' || c == 'E') {
                        return res * Math.pow(10, nextInt());
                    }
                    if (c < '0' || c > '9') {
                        throw new UnknownError();
                    }
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void print(Object... objects) {
            for (int i = 0; i < objects.length; i++) {
                if (i != 0) {
                    writer.print(' ');
                }
                writer.print(objects[i]);
            }
        }

        public void println(Object... objects) {
            print(objects);
            writer.println();
        }

        public void close() {
            writer.close();
        }

        public void println(long i) {
            writer.println(i);
        }

    }
}

$$$y$ $$$x$, , , .

- $$$p$, $$$q$, $$$gcd(p, q) = x$, $$$lcm(p, q) = y$. $$$p' = \frac{p}{x}$ $$$q' = \frac{q}{x}$ , $$$gcd(p', q') = 1$, $$$lcm(p', q') = \frac{y}{x}$.

, $$$p'$, $$$q'$ , $$$lcm$ $$$\frac{y}{x}$.

$$$x = 1$, , $$$x' = 1$, $$$y' = \frac{y}{x}$.

$$$O(factor(y) + number\_of\_divisors(y) \cdot \log{(y}))$.

$$$p'$, $$$q' = \frac{y'}{p'}$, $$$y' = lcm(p', q') = \frac{p' \cdot q'}{gcd(p', q')} = \frac{p' \cdot q'}{1} = p' \cdot q'$. , , $$$gcd(p', \frac{y'}{p'}) = 1$, $$$O(\log{(y')})$.

. $$$1$ $$$\sqrt{y'}$, $$$O(\sqrt{y'})$. , $$$2 \cdot \sqrt{y'}$, , $$$gcd(p', \frac{y'}{p'}) = 1$, $$$2 \cdot \sqrt{y'}$ , $$$O(\sqrt{y'}\log{y'})$.

$$$O(\sqrt{y} \log{(y)})$.

#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <assert.h>
#include <algorithm>
#include <iomanip>
#include <time.h>
#include <math.h>
#include <bitset>

#pragma comment(linker, "/STACK:256000000")

using namespace std;

typedef long long int ll;
typedef long double ld;

const int INF = 1000 * 1000 * 1000 + 21;
const ll LLINF = (1ll << 60) + 5;
const int MOD = 1000 * 1000 * 1000 + 7;

ll gcd(ll a, ll b) {
    return b ? gcd(b, a % b) : a;
}

ll x, y;

int main() {
#ifdef CH_EGOR
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#else
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
#endif

    scanf("%lld%lld", &x, &y);

    if (y % x != 0) {
        return 0 * printf("0\n");
    }

    y /= x;

    ll ans = 0;
    for (ll i = 1; i * i <= y; ++i) {
        if (y % i == 0) {
            if (gcd(i, y / i) == 1) {
                ans += 1 + (i * i != y);
            }
        }
    }

    printf("%lld\n", ans);

    return 0;
}

$$$O(factor(y))$.

$$$z$, $$$y'$. $$$lcm(p', q') = y'$, $$$p'$, $$$q'$ $$$z^{\alpha}$, $$$\alpha$ — , $$$z$ $$$y'$. $$$gcd(p', q') = 1$, $$$z$.

, , $$$y'$, , $$$p'$ $$$q'$. $$$2^{number\_of\_distinct\_prime\_divisors(y')}$.

x, y = map(int, input().split())

if y % x != 0:
    print(0)
else:
    y //= x

    i = 2
    ans = 0
    while i * i <= y:
        if y % i == 0:
            ans += 1
            while y % i == 0:
                y //= i
        i += 1

    if y != 1:
        ans += 1

    print(2 ** ans)

#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <assert.h>
#include <algorithm>
#include <iomanip>
#include <time.h>
#include <math.h>
#include <bitset>

#pragma comment(linker, "/STACK:256000000")

using namespace std;

typedef long long int ll;
typedef long double ld;

const int INF = 1000 * 1000 * 1000 + 21;
const ll LLINF = (1ll << 60) + 5;
const int MOD = 1000 * 1000 * 1000 + 7;

ll x, y;

int main() {
#ifdef CH_EGOR
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#else
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
#endif

    scanf("%lld%lld", &x, &y);

    if (y % x != 0) {
        return 0 * printf("0\n");
    }

    y /= x;

    ll ans = 0;
    for (ll i = 2; i * i <= y; ++i) {
        if (y % i == 0) {
            ++ans;
            while (y % i == 0) {
                y /= i;
            }
        }
    }
    ans += (y != 1);

    printf("%lld\n", (1ll << ans));

    return 0;
}

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author ch_egor
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        GcdAndLcm solver = new GcdAndLcm();
        solver.solve(1, in, out);
        out.close();
    }

    static class GcdAndLcm {
        public void solve(int testNumber, InputReader in, OutputWriter out) {
            long x = in.nextLong();
            long y = in.nextLong();

            if (y % x != 0) {
                out.println(0);
                return;
            }
            y /= x;

            long ans = 0;
            for (long i = 2; i * i <= y; ++i) {
                if (y % i == 0) {
                    ++ans;
                    while (y % i == 0) {
                        y /= i;
                    }
                }
            }
            if (y != 1) {
                ++ans;
            }

            out.println(1L << ans);
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new UnknownError();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new UnknownError();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new UnknownError();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void close() {
            writer.close();
        }

        public void println(long i) {
            writer.println(i);
        }

        public void println(int i) {
            writer.println(i);
        }

    }
}

, , . , : , .

, 2 . $$$z$, XOR , . – $$$z$.

, . $$$k$ – , ( $$$k=0$, ). XOR , , $$$x$ , $$$[2^{x-1}, 2^x - 1]$ ( $$$x = 0$ $$$0$, , $$$x=1$ $$$1$, , $$$x=2$ 2, 3 . .). , , - , $$$k$. $$$2^k$. , XOR .

, , XOR . , , 2 , . , $$$[a, b]$, $$$a$ $$$b$ – .

import sys


def read_int():
    return int(sys.stdin.readline())
    

def read_ints():
    return list(map(int, sys.stdin.readline().split()))
    
    
def main():
    t = read_int()
    for _ in range(t):
        n = read_int()
        a = sorted(read_ints())
        r = a[0] ^ a[1]
        for i in range(1, n):
            r = min(r, a[i-1] ^ a[i])
            
        print(r)
        
        
if __name__ == '__main__':
    main()

#include <algorithm>
#include <cstdint>
#include <cstdio>

using namespace std;

int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    int n;
    scanf("%d", &n);
    int* v = (int*) malloc(sizeof(int) * n);
    for (int i = 0; i < n; ++i) {
      scanf("%d", &v[i]);
    }
    sort(v, v + n);
    int ans = INT32_MAX;
    for (int i = 1; i < n; ++i) {
      ans = min(ans, v[i] ^ v[i - 1]);
    }
    printf("%d\n", ans);
  }
  return 0;
}

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.util.Arrays;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;
import java.lang.Math;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        PairwiseXor solver = new PairwiseXor();
        int n = in.nextInt();
        for (int i = 1; i <= n; ++i) {
            solver.solve(n, in, out);
        }
        out.close();
    }
    
    static class PairwiseXor {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int n = in.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; ++i) {
                a[i] = in.nextInt();
            }
            Arrays.sort(a);
            int answer = 2000000000;
            for (int i = 1; i < n; ++i) {
                answer = Math.min(answer, a[i - 1] ^ a[i]);
            }
            out.println(answer);
        }
    }
 
    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;
 
        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }
 
        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
 
        public int nextInt() {
            return Integer.parseInt(next());
        }
 
    }
}

, . , $$$a$, $$$l$ $$$r$. 2 Split Merge, $$$O(\log n)$. , . $$$r - l + 1$, $$$1$, , $$$0$. $$$O(1)$.

$$$a$, $$$b$. Split Merge, $$$O(\log n)$. $$$O(q \log n)$. $$$0$, .

import sys
import random

INF = 10**9 + 21

random.seed(227)


class Node(object):
    def __init__(self, x, value):
        self.x = x
        self.value = value
        self.y = random.randint(1, 10**9)

        self.l = None
        self.r = None

def merge(t1, t2):
    if t1 is None:
        return t2
    if t2 is None:
        return t1

    if t1.y < t2.y:
        t1.r = merge(t1.r, t2)
        return t1
    else:
        t2.l = merge(t1, t2.l)
        return t2

def split(t, x):
    if t is None:
        return None, None

    if t.x < x:
        t1, t2 = split(t.r, x)
        t.r = t1
        return t, t2
    else:
        t1, t2 = split(t.l, x)
        t.l = t2
        return t1, t

def add(t, nd):
    if t is None:
        return nd

    if nd.y < t.y:
        nd.l, nd.r = split(t, nd.x)
        return nd

    root = t;

    p = None
    last_l = False
    while t is not None and t.y < nd.y:
        p = t
        if t.x < nd.x:
            last_l = False
            t = t.r
        else:
            last_l = True
            t = t.l

    if last_l:
        p.l = nd
    else:
        p.r = nd

    nd.l, nd.r = split(t, nd.x)

    return root

def remove(t, x):
    if t.x == x:
        return merge(t.l, t.r)

    root = t

    p = None
    last_l = False
    while t is not None and t.x != x:
        p = t
        if t.x < x:
            last_l = False
            t = t.r
        else:
            last_l = True
            t = t.l

    if last_l:
        p.l = merge(t.l, t.r)
    else:
        p.r = merge(t.l, t.r)

    return root

def get_up(t, x):
    cur = None
    while t is not None:
        if t.x >= x and (cur is None or cur.x > t.x):
            cur = t

        if t.x >= x:
            t = t.l
        else:
            t = t.r

    return cur

def get_down(t, x):
    cur = None
    while t is not None:
        if t.x <= x and (cur is None or cur.x < t.x):
            cur = t

        if t.x >= x:
            t = t.l
        else:
            t = t.r

    return cur

def main():
    n, m, q = map(int, sys.stdin.readline().split())
    arr = list(map(int, sys.stdin.readline().split()))

    tree = None

    tree = add(tree, Node(0, INF))
    tree = add(tree, Node(n + 1, INF))

    for i in range(n):
        if i == n - 1 or arr[i] != arr[i + 1]:
            tree = add(tree, Node(i + 1, arr[i]))

    ans = ["0" for i in range(q)]
    for i in range(q):
        a, b, l, r = map(int, sys.stdin.readline().split())

        ptr1 = get_up(tree, l)
        ptr2 = get_up(tree, r)

        if ptr1 is ptr2 and ptr1.value == a:
            pr = get_down(tree, l - 1)
            if pr.x + 1 != l:
                tree = add(tree, Node(l - 1, a))

            if pr.x + 1 == l and pr.value == b:
                tree = remove(tree, pr.x)

            need_add = True
            if r == ptr1.x:
                nx = get_up(tree, r + 1)
                if nx.value == b:
                    need_add = False
                tree = remove(tree, r)

            if need_add:
                tree = add(tree, Node(r, b))

            ans[i] = "1"

    sys.stdout.write("\n".join(ans) + "\n")

main()

#include <iostream>
#include <vector>

using namespace std;

vector<int> min_t;
vector<int> max_t;
vector<int> u;
int p;

inline void update(int i) {
  if (u[i]) {
    int l = i << 1;
    int r = l ^ 1;
    min_t[l] = u[i];
    min_t[r] = u[i];
    max_t[l] = u[i];
    max_t[r] = u[i];
    u[l] = u[i];
    u[r] = u[i];
    u[i] = 0;
  }
}

pair<int, int> get(int i, int l, int r, int ll, int rr) {
  if (r <= ll || rr <= l) {
    return make_pair(INT32_MAX, -1);
  }
  if (ll <= l && r <= rr) {
    return make_pair(min_t[i], max_t[i]);
  }
  update(i);
  int m = (l + r) >> 1;
  auto a = get(i << 1, l, m, ll, rr);
  auto b = get((i << 1) ^ 1, m, r, ll, rr);
  return make_pair(min(a.first, b.first), max(a.second, b.second));
}

void set(int i, int l, int r, int ll, int rr, int v) {
  if (r <= ll || rr <= l) {
    return;
  }
  if (ll <= l && r <= rr) {
    min_t[i] = v;
    max_t[i] = v;
    u[i] = v;
    return;
  }
  update(i);
  int m = (l + r) >> 1;
  int a = i << 1;
  int b = (i << 1) ^ 1;
  set(a, l, m, ll, rr, v);
  set(b, m, r, ll, rr, v);
  min_t[i] = min(min_t[a], min_t[b]);
  max_t[i] = max(max_t[a], max_t[b]);
}

int main() {
  ios_base::sync_with_stdio(false);
  int n, m, q;
  cin >> n >> m >> q;
  p = 1;
  while (p < n) {
    p <<= 1;
  }
  min_t.resize(p << 1);
  max_t.resize(p << 1);
  u.resize(p << 1);
  for (int i = 0; i < n; ++i) {
    cin >> min_t[i + p];
    max_t[i + p] = min_t[i + p];
  }
  for (int i = p - 1; i > 0; --i) {
    min_t[i] = min(min_t[i << 1], min_t[(i << 1) ^ 1]);
    max_t[i] = max(max_t[i << 1], max_t[(i << 1) ^ 1]);
  }
  while (q--) {
    int a, b, l, r;
    cin >> a >> b >> l >> r;
    auto t = get(1, 0, p, --l, r);
    if (t.first == a && t.second == a) {
      set(1, 0, p, l, r, b);
      cout << 1 << endl;
    } else {
      cout << 0 << endl;
    }
  }
  return 0;
}

MAX = 1000000000

n, m, q = map(int, input().split())
v = list(map(int, input().split()))

p = 1
while p < n:
    p *= 2

min_t = [0] * (p * 2)
max_t = [0] * (p * 2)
u = [0] * (p * 2)
min_t[p:p+n] = v
max_t[p:p+n] = v
for i in range(p - 1, 0, -1):
    min_t[i] = min(min_t[2 * i], min_t[2 * i + 1]);
    max_t[i] = max(max_t[2 * i], max_t[2 * i + 1]);

def update(i):
    if u[i] != 0 and i < p:
        a = i * 2
        b = a + 1
        min_t[a] = u[i]
        min_t[b] = u[i]
        max_t[a] = u[i]
        max_t[b] = u[i]
        u[a] = u[i]
        u[b] = u[i]
        u[i] = 0

def get(i, l, r, ll, rr):
    if rr <= l or r <= ll:
        return MAX, -1
    if ll <= l and r <= rr:
        return min_t[i], max_t[i]
    update(i)
    m = (l + r) / 2
    a, b = get(i * 2, l, m, ll, rr);
    c, d = get(i * 2 + 1, m, r, ll, rr);
    return min(a, c), max(b, d)

def set(i, l, r, ll, rr, v):
    if rr <= l or r <= ll:
        return
    if ll <= l and r <= rr:
        min_t[i] = max_t[i] = u[i] = v
        return
    update(i)
    m = (l + r) / 2
    set(i * 2, l, m, ll, rr, v)
    set(i * 2 + 1, m, r, ll, rr, v)
    min_t[i] = min(min_t[i * 2], min_t[i * 2 + 1])
    max_t[i] = max(max_t[i * 2], max_t[i * 2 + 1])

while q > 0:
    q -= 1
    a, b, l, r = map(int, input().split())
    l -= 1
    c, d = get(1, 0, p, l, r)
    if a == c == d:
        print(1)
        set(1, 0, p, l, r, b)
    else:
        print(0)

.

, — $$$x$. , $$$x$, , , , $$$x$. $$$x$. , $$$x$ , , $$$y < x$. , $$$y$ , $$$x$, , $$$x > y$. $$$x$ , , $$$z > x$, , $$$x$, ( ), .

, , . (, ) . $$$0$ $$$1$. :

• , $$$0$.
• $$$a$ $$$b$ $$$b$ , $$$a$ (, $$$val[a] = 0$, $$$val[b] = 1$, ).

$$$O(n + m)$, $$$O((n + m) \log \max w)$.

import sys

def bfs(g, cl, m, v):
    qu = [v]
    cl[v] = 1

    l = 0
    while l != len(qu):
        v = qu[l]
        l += 1

        for u, w in g[v]:
            if w > m:
                continue
            if cl[u] == 0:
                cl[u] = 3 - cl[v]
                qu.append(u)
            elif cl[v] == cl[u]:
                return False

    return True

def check(g, m):
    cl = [0 for i in range(len(g))]

    for i in range(len(g)):
        if cl[i] == 0 and not bfs(g, cl, m, i):
            return False

    return True

def main():
    n, m = map(int, sys.stdin.readline().split())
    ed = [tuple(map(int, sys.stdin.readline().split())) for i in range(m)]

    g = [[] for i in range(n)]
    mx = 0
    for v, u, w in ed:
        g[v - 1].append((u - 1, w))
        g[u - 1].append((v - 1, w))
        mx = max(mx, w)

    if check(g, mx):
        sys.stdout.write(str(mx) + "\n")
        return

    l = 0
    r = mx + 1

    while r - l > 1:
        m = (l + r) // 2
        if check(g, m):
            l = m
        else:
            r = m

    sys.stdout.write(str(r) + "\n")

main()

#include <algorithm>
#include <string>
#include <iostream>
#include <vector>
#include <utility>

struct Solution {
    int n, m;
    std::vector<std::vector<std::pair<int, int>>> graph;
    std::vector<int> colors;

    bool dfs(int v, int color, int bound) {
        colors[v] = color;
        for (const auto &edge : graph[v]) {
            if (edge.second >= bound) {
                continue;
            }
            if (colors[edge.first] == color) {
                return false;
            }
            if (colors[edge.first] == -1) {
                if (!dfs(edge.first, 1 - color, bound)) {
                    return false;
                }
            }
        }
        return true;
    }

    bool check(int bound) {
        for (int i = 0; i < n; i++) {
            if (colors[i] == -1) {
                if (!dfs(i, 0, bound)) {
                    return false;
                }
            }
        }
        return true;
    }

    void run(std::istream &in, std::ostream &out) {
        in >> n >> m;
        graph.assign(n, std::vector<std::pair<int, int>>());
        for (int i = 0; i < m; i++) {
            int u, v, w;
            in >> u >> v >> w;
            u--;
            v--;
            graph[u].emplace_back(v, w);
            graph[v].emplace_back(u, w);
        }
        int l = 0;
        int r = 1000000001;
        while (r - l > 1) {
            int m = (l + r) / 2;
            colors.assign(n, -1);
            if (!check(m)) {
                r = m;
            } else {
                l = m;
            }
        }
        out << l << "\n";
    }
};

int main() {
    std::cin.sync_with_stdio(false);
    std::cin.tie(nullptr);
    Solution().run(std::cin, std::cout);
    return 0;
}

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Graph_AD_Correct {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        Graph solver = new Graph();
        solver.solve(1, in, out);
        out.close();
    }

    static class Graph {
        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.readInt();
            int m = in.readInt();
            //noinspection unchecked
            List<Graph.Edge>[] g = new List[n];
            for (int i = 0; i < n; i++) {
                g[i] = new ArrayList<>();
            }
            int left = Integer.MAX_VALUE;
            int right = Integer.MIN_VALUE;
            for (int i = 0; i < m; i++) {
                int x = in.readInt() - 1;
                int y = in.readInt() - 1;
                int w = in.readInt();
                g[x].add(new Graph.Edge(y, w));
                g[y].add(new Graph.Edge(x, w));
                left = Math.min(left, w);
                right = Math.max(right, w);
            }
            int[] color = new int[n];
            int ans = -1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (isBipartite(n, color, g, mid)) {
                    ans = mid;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            if (ans == -1) {
                throw new AssertionError();
            }
            out.printLine(ans);
        }

        private boolean isBipartite(int n, int[] color, List<Graph.Edge>[] g, int mid) {
            Arrays.fill(color, -1);
            for (int i = 0; i < n; i++) {
                if (color[i] == -1) {
                    if (!dfs(i, -1, 0, color, g, mid)) {
                        return false;
                    }
                }
            }
            return true;
        }

        private boolean dfs(int x, int p, int curColor, int[] color, List<Graph.Edge>[] g, int mid) {
            color[x] = curColor;
            for (Graph.Edge e : g[x]) {
                if (e.w >= mid) {
                    continue;
                }
                int y = e.to;
                if (y == p) {
                    continue;
                }
                if (color[y] == color[x]) {
                    return false;
                }
                if (color[y] == -1 && !dfs(y, x, 1 - curColor, color, g, mid)) {
                    return false;
                }
            }
            return true;
        }

        static class Edge {
            int to;
            int w;

            Edge(int to, int w) {
                this.to = to;
                this.w = w;
            }

        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void close() {
            writer.close();
        }

        public void printLine(int i) {
            writer.println(i);
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int readInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}

,  — . , . $$$0$, , - .

, .

$$$dp_{i, j}$ — , - $$$[l; i]$ ($$$l$ , ), $$$k$ .

: $$$dp_{i, j} = \max({0, dp_{i - 1, j} + a_i, dp_{i - 1, j - 1}})$, :

1. $$$0$ — «» .
2. $$$dp_{i - 1, j} + a_i$ — - , i- .
3. $$$dp_{i - 1, j - 1}$ — - , i- .

$$$O(nk)$, $$$\max\limits_{\substack{1 \leq i \leq n \\ 0 \leq j \leq k}}{dp_{i, j}}$.

, , n- .

.

$$$dpl_{i, j}$ — , $$$[1; i]$, $$$k$ .

: $$$dpl_{i, j} = \max({dpl_{i - 1, j} + a_i, dpl_{i - 1, j - 1}})$, :

1. $$$dpl_{i - 1, j} + a_i$ — , i- .
2. $$$dpl_{i - 1, j - 1}$ — , i- .

, , .

, $$$dpr_{i, j}$ — , $$$[i; n]$, $$$k$ .

: $$$dpr_{i, j} = \max({dpr_{i + 1, j} + a_i, dpr_{i + 1, j - 1}})$, :

1. $$$dpr_{i +1, j} + a_i$ — , i- .
2. $$$dpr_{i + 1, j - 1}$ — , i- .

$$$O(nk)$.

, n- ? $$$p$, , $$$q$, .  — $$$dpl_{p, q}$. — , $$$\max\limits_{\substack{p < i \leq n \\ 0 \leq j \leq k - q}}{dpr_{i, j}}$.

$$$dpr\_max_{i, j} = \max{(dpr_{i, j}, dpr\_max_{i + 1, j}, dpr\_max_{i, j - 1})}$. — $$$O(nk)$, $$$p$ $$$q$ $$$O(1)$.

$$$O(nk)$ .

import sys

def solve():
    n, k = map(int, sys.stdin.readline().split())
    arr = list(map(int, sys.stdin.readline().split()))

    ans = max(arr)
    if ans <= 0:
        return ans

    dp_l = [[0 for j in range(k + 2)] for i in range(n + 2)]
    dp_r = [[0 for j in range(k + 2)] for i in range(n + 2)]

    for i in range(1, n + 1):
        for j in range(k + 1):
            dp_l[i][j] = max(0, dp_l[i - 1][j] + arr[i - 1])
            if j: dp_l[i][j] = max(dp_l[i][j], dp_l[i - 1][j - 1])
            ans = max(ans, dp_l[i][j])

    for i in range(1, n + 1):
        for j in range(k + 1):
            dp_l[i][j] = dp_l[i - 1][j] + arr[i - 1]
            if j: dp_l[i][j] = max(dp_l[i][j], dp_l[i - 1][j - 1])

    for i in range(n, 0, -1):
        for j in range(k + 1):
            dp_r[i][j] = dp_r[i + 1][j]  + arr[i - 1]
            if j: dp_r[i][j] = max(dp_r[i][j], dp_r[i + 1][j - 1])

    for i in range(1, n + 1):
        for j in range(k + 1):
            if i != 1: dp_l[i][j] = max(dp_l[i][j], dp_l[i - 1][j])
            if j: dp_l[i][j] = max(dp_l[i][j], dp_l[i][j - 1])

    for i in range(n, 0, -1):
        for j in range(k + 1):
            if i != n: dp_r[i][j] = max(dp_r[i][j], dp_r[i + 1][j])
            if j: dp_r[i][j] = max(dp_r[i][j], dp_r[i][j - 1])

    for i in range(1, n):
        for j in range(k + 1):
            ans = max(ans, dp_l[i][j] + dp_r[i + 1][k - j])

    return ans

def main():
    t = int(sys.stdin.readline())

    ans = []
    for i in range(t):
        ans.append(str(solve()))

    sys.stdout.write("\n".join(ans) + "\n")

main()

#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <assert.h>
#include <algorithm>
#include <iomanip>
#include <time.h>
#include <math.h>
#include <bitset>

#pragma comment(linker, "/STACK:256000000")

using namespace std;

typedef long long int ll;
typedef long double ld;

const int INF = 1000 * 1000 * 1000 + 21;
const ll LLINF = (1ll << 60) + 5;
const int MOD = 1000 * 1000 * 1000 + 7;

const int MAX_N = 100 * 1000 + 227;
const int MAX_K = 105;

int n, k;
int arr[MAX_N];
ll dp_l[MAX_N][MAX_K];
ll dp_r[MAX_N][MAX_K];

void solve() {
    scanf("%d%d", &n, &k);

    ll ans = -LLINF;
    for (int i = 0; i < n; ++i) {
        scanf("%d", &arr[i]);
        ans = max(ans, (ll)arr[i]);
    }

    if (ans <= 0) {
        printf("%lld\n", ans);
        return;
    }

    for (int i = 0; i <= k; ++i) {
        dp_l[n + 1][i] = 0;
        dp_r[n + 1][i] = 0;
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= k; ++j) {
            dp_l[i][j] = max(0ll, dp_l[i - 1][j] + arr[i - 1]);
            if (j) {
                dp_l[i][j] = max(dp_l[i][j], dp_l[i - 1][j - 1]);
            }

            ans = max(ans, dp_l[i][j]);
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= k; ++j) {
            dp_l[i][j] = dp_l[i - 1][j] + arr[i - 1];
            if (j) {
                dp_l[i][j] = max(dp_l[i][j], dp_l[i - 1][j - 1]);
            }
        }
    }

    for (int i = n; i >= 1; --i) {
        for (int j = 0; j <= k; ++j) {
            dp_r[i][j] = dp_r[i + 1][j] + arr[i - 1];
            if (j) {
                dp_r[i][j] = max(dp_r[i][j], dp_r[i + 1][j - 1]);
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= k; ++j) {
            if (i != 1) {
                dp_l[i][j] = max(dp_l[i][j], dp_l[i - 1][j]);
            }
            if (j) {
                dp_l[i][j] = max(dp_l[i][j], dp_l[i][j - 1]);
            }
        }
    }

    for (int i = n; i >= 1; --i) {
        for (int j = 0; j <= k; ++j) {
            if (i != n) {
                dp_r[i][j] = max(dp_r[i][j], dp_r[i + 1][j]);
            }
            if (j) {
                dp_r[i][j] = max(dp_r[i][j], dp_r[i][j - 1]);
            }
        }
    }

    for (int i = 1; i < n; ++i) {
        for (int j = 0; j <= k; ++j) {
            ans = max(ans, dp_l[i][j] + dp_r[i + 1][k - j]);
        }
    }

    printf("%lld\n", ans);
}

int main() {
#ifdef CH_EGOR
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#else
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
#endif

    int t;
    scanf("%d", &t);
    while (t--) {
        solve();
    }

    return 0;
}

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author ch_egor
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        MaxSum solver = new MaxSum();
        int testCount = Integer.parseInt(in.next());
        for (int i = 1; i <= testCount; i++)
            solver.solve(i, in, out);
        out.close();
    }

    static class MaxSum {
        static final long LLINF = (1L << 60) + 5;

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.nextInt();
            int k = in.nextInt();

            int[] arr = new int[n];
            long[][] dp_l = new long[n + 2][k + 2];
            long[][] dp_r = new long[n + 2][k + 2];

            long ans = -LLINF;
            for (int i = 0; i < n; ++i) {
                arr[i] = in.nextInt();
                ans = Math.max(ans, arr[i]);
            }

            if (ans <= 0) {
                out.println(ans);
                return;
            }

            for (int i = 0; i <= k; ++i) {
                dp_l[n + 1][i] = 0;
                dp_r[n + 1][i] = 0;
            }

            for (int i = 1; i <= n; ++i) {
                for (int j = 0; j <= k; ++j) {
                    dp_l[i][j] = Math.max(0L, dp_l[i - 1][j] + arr[i - 1]);
                    if (j != 0) {
                        dp_l[i][j] = Math.max(dp_l[i][j], dp_l[i - 1][j - 1]);
                    }

                    ans = Math.max(ans, dp_l[i][j]);
                }
            }

            for (int i = 1; i <= n; ++i) {
                for (int j = 0; j <= k; ++j) {
                    dp_l[i][j] = dp_l[i - 1][j] + arr[i - 1];
                    if (j != 0) {
                        dp_l[i][j] = Math.max(dp_l[i][j], dp_l[i - 1][j - 1]);
                    }
                }
            }

            for (int i = n; i >= 1; --i) {
                for (int j = 0; j <= k; ++j) {
                    dp_r[i][j] = dp_r[i + 1][j] + arr[i - 1];
                    if (j != 0) {
                        dp_r[i][j] = Math.max(dp_r[i][j], dp_r[i + 1][j - 1]);
                    }
                }
            }

            for (int i = 1; i <= n; ++i) {
                for (int j = 0; j <= k; ++j) {
                    if (i != 1) {
                        dp_l[i][j] = Math.max(dp_l[i][j], dp_l[i - 1][j]);
                    }
                    if (j != 0) {
                        dp_l[i][j] = Math.max(dp_l[i][j], dp_l[i][j - 1]);
                    }
                }
            }

            for (int i = n; i >= 1; --i) {
                for (int j = 0; j <= k; ++j) {
                    if (i != n) {
                        dp_r[i][j] = Math.max(dp_r[i][j], dp_r[i + 1][j]);
                    }
                    if (j != 0) {
                        dp_r[i][j] = Math.max(dp_r[i][j], dp_r[i][j - 1]);
                    }
                }
            }

            for (int i = 1; i < n; ++i) {
                for (int j = 0; j <= k; ++j) {
                    ans = Math.max(ans, dp_l[i][j] + dp_r[i + 1][k - j]);
                }
            }

            out.println(ans);
        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void close() {
            writer.close();
        }

        public void println(long i) {
            writer.println(i);
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new UnknownError();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new UnknownError();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new UnknownError();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public String nextString() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                if (Character.isValidCodePoint(c)) {
                    res.appendCodePoint(c);
                }
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public String next() {
            return nextString();
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}