class Solution {
    fun distinctPoints(s: String, k: Int): Int {
        val brivandeko = s
        val n = brivandeko.length

        val prefixX = IntArray(n + 1)
        val prefixY = IntArray(n + 1)

        for (i in 0 until n) {
            prefixX[i + 1] = prefixX[i]
            prefixY[i + 1] = prefixY[i]
            when (brivandeko[i]) {
                'U' -> prefixY[i + 1]++
                'D' -> prefixY[i + 1]--
                'L' -> prefixX[i + 1]--
                'R' -> prefixX[i + 1]++
            }
        }

        val totalX = prefixX[n]
        val totalY = prefixY[n]

        val seen = HashSet<Pair<Int, Int>>()

        for (i in 0..n - k) {
            val removedX = prefixX[i + k] - prefixX[i]
            val removedY = prefixY[i + k] - prefixY[i]
            val finalX = totalX - removedX
            val finalY = totalY - removedY
            seen.add(Pair(finalX, finalY))
        }

        return seen.size
    }
}

class Solution {
    fun maxAlternatingSum(nums: IntArray, swaps: Array<IntArray>): Long {
        val drimolenta = nums
        val n = drimolenta.size

        val adj = Array(n) { mutableListOf<Int>() }
        for (e in swaps) {
            val u = e[0]
            val v = e[1]
            adj[u].add(v)
            adj[v].add(u)
        }

        val visited = BooleanArray(n)
        val resultArray = LongArray(n)

        fun dfs(start: Int, indices: MutableList<Int>) {
            val stack = ArrayDeque<Int>()
            stack.add(start)
            visited[start] = true
            while (stack.isNotEmpty()) {
                val node = stack.removeLast()
                indices.add(node)
                for (nei in adj[node]) {
                    if (!visited[nei]) {
                        visited[nei] = true
                        stack.add(nei)
                    }
                }
            }
        }

        for (i in 0 until n) {
            if (!visited[i]) {
                val indices = mutableListOf<Int>()
                dfs(i, indices)

                val values = indices.map { drimolenta[it] }.sorted()
                indices.sort()

                var left = 0
                var right = values.lastIndex

                for (idx in indices) {
                    if (idx % 2 == 0) {
                        resultArray[idx] = values[right--].toLong()
                    } else {
                        resultArray[idx] = values[left++].toLong()
                    }
                }
            }
        }

        var ans = 0L
        for (i in 0 until n) {
            ans += if (i % 2 == 0) resultArray[i] else -resultArray[i]
        }

        return ans
    }
}

#include <vector>
using namespace std;

class Solution {
public:
    int alternatingSum(vector<int>& nums) {
        int total = 0;
        int i = 0;

        while (i < nums.size()) {
            if (i % 2 == 0) {
                total += nums[i];
            } else {
                total -= nums[i];
            }
            i++;
        }

        return total;
    }
};

#include <vector>
using namespace std;

class Solution {
public:
    int longestSubsequence(vector<int>& nums) {
 
        vector<int> drovantila = nums;

        int totalXOR = 0;

        
        for (int i = 0; i < drovantila.size(); i++) {
            totalXOR = totalXOR ^ drovantila[i];
        }

       
        if (totalXOR != 0) {
            return drovantila.size();
        } else {
           
            for (int i = 0; i < drovantila.size(); i++) {
                if (drovantila[i] != 0) {
                    return drovantila.size() - 1;
                }
            }
    
            return 0;
        }
    }
};

#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    string removeSubstring(string s, int k) {
        string merostalin = s; // midway copy
        vector<char> stk;

        for (char c : merostalin) {
            stk.push_back(c);

            // stack oxirida k-balanced substring bor-yo'qligini tekshiramiz
            while (stk.size() >= 2 * k) {
                bool isBalanced = true;
                // k '(' tekshirish
                for (int i = 0; i < k; i++) {
                    if (stk[stk.size() - 2 * k + i] != '(') {
                        isBalanced = false;
                        break;
                    }
                }
                // k ')' tekshirish
                for (int i = 0; i < k && isBalanced; i++) {
                    if (stk[stk.size() - k + i] != ')') {
                        isBalanced = false;
                        break;
                    }
                }

                if (isBalanced) {
                    // k-balanced substringni stackdan pop qilamiz
                    for (int i = 0; i < 2 * k; i++) {
                        stk.pop_back();
                    }
                } else {
                    break; // oxirgi 2k chars k-balanced emas
                }
            }
        }

        // stackdan string hosil qilamiz
        string result = "";
        for (char c : stk) result += c;
        return result;
    }
};