A binary string is a string consisting only of 0s and 1s. A substring is a contiguous group of characters within a string.

Given a binary string, find the number of substrings that contain an equal number of 0s and 1s and all the 0s and 1s are grouped together. Note that duplicate substrings are also counted in the answer. For example, "0011" has two overlapping substrings that meet the criteria: "0011" and "01".

Example: s = "00110011" → 6.

解法

将连续相同字符合成游程；相邻两段贡献 min(prev, cur) 个合法子串。复杂度 O(n)。

def getSubstringCount(s: str) -> int:
    groups = []
    cnt = 1
    for i in range(1, len(s)):
        if s[i] == s[i - 1]: cnt += 1
        else: groups.append(cnt); cnt = 1
    groups.append(cnt)
    return sum(min(groups[i], groups[i + 1]) for i in range(len(groups) - 1))

class Solution {
    static long getSubstringCount(String s) {
        long ans = 0, prev = 0, cur = 1;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i - 1)) cur++;
            else { ans += Math.min(prev, cur); prev = cur; cur = 1; }
        }
        return ans + Math.min(prev, cur);
    }
}

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

long long getSubstringCount(string s) {
 long long ans = 0, prev = 0, cur = 1;
 for (int i = 1; i < (int)s.size(); i++) {
 if (s[i] == s[i - 1]) cur++;
 else { ans += min(prev, cur); prev = cur; cur = 1; }
 }
 return ans + min(prev, cur);
}

A popular social media platform provides a feature to connect people online. Connections are represented as an undirected graph where a user can see the profiles of those they are connected to (directly or transitively).

Given connection_nodes users, connection_edges edges in arrays connection_from[] and connection_to[], and a queries[] array, return for each query queries[i] the number of users whose profiles are visible to user queries[i] (i.e., the size of the connected component containing that user).

connection_nodes = 7
edges: (1,2), (2,3), (3,4), (5,6)
queries = [1, 3, 5, 7]
→ [4, 4, 2, 1]

解法

带大小的并查集。先把所有边加入 DSU，每次查询返回 size[find(q)]。复杂度 O((E + Q) · α(N))。

def getVisibleProfilesCount(n, c_from, c_to, queries):
    parent = list(range(n + 1))
    size = [1] * (n + 1)
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    def union(a, b):
        a, b = find(a), find(b)
        if a == b: return
        if size[a] < size[b]: a, b = b, a
        parent[b] = a; size[a] += size[b]
    for u, v in zip(c_from, c_to):
        union(u, v)
    return [size[find(q)] for q in queries]

class Solution {
    int[] parent, size;
    int find(int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }
    void union_(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return;
        if (size[a] < size[b]) { int t = a; a = b; b = t; }
        parent[b] = a; size[a] += size[b];
    }
    int[] getVisibleProfilesCount(int n, int[] from_, int[] to_, int[] queries) {
        parent = new int[n + 1]; size = new int[n + 1];
        for (int i = 0; i <= n; i++) { parent[i] = i; size[i] = 1; }
        for (int i = 0; i < from_.length; i++) union_(from_[i], to_[i]);
        int[] out = new int[queries.length];
        for (int i = 0; i < queries.length; i++) out[i] = size[find(queries[i])];
        return out;
    }
}

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

class DSU {
public:
    vector<int> parent, size;
    DSU(int n) : parent(n + 1), size(n + 1, 1) { iota(parent.begin(), parent.end(), 0); }
    int find(int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }
    void unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return;
        if (size[a] < size[b]) swap(a, b);
        parent[b] = a; size[a] += size[b];
    }
};

vector<int> getVisibleProfilesCount(int n, vector<int>& from_, vector<int>& to_, vector<int>& queries) {
    DSU d(n);
    for (int i = 0; i < (int)from_.size(); i++) d.unite(from_[i], to_[i]);
    vector<int> out;
    for (int q : queries) out.push_back(d.size[d.find(q)]);
    return out;
}

Determine the number of valid words in a given string s. A valid word contains:

• At least 3 characters.
• Only alphanumeric characters (i.e., the numbers 0–9, letters A–Z in either case).
• At least one vowel (a, e, i, o, u).
• At least one consonant.

解法

按空白切分；每个 token 检查长度 ≥ 3、全是字母数字、至少一个元音和一个辅音。复杂度 O(|s|)。

def countValidWords(s: str) -> int:
    VOWELS = set('aeiouAEIOU')
    cnt = 0
    for w in s.split():
        if len(w) < 3 or not w.isalnum():
            continue
        has_v = any(c in VOWELS for c in w)
        has_c = any(c.isalpha() and c not in VOWELS for c in w)
        if has_v and has_c:
            cnt += 1
    return cnt

import java.util.*;

class Solution {
    static int countValidWords(String s) {
        Set<Character> V = Set.of('a','e','i','o','u','A','E','I','O','U');
        int cnt = 0;
        for (String w : s.split("\\s+")) {
            if (w.length() < 3) continue;
            boolean alnum = true, hv = false, hc = false;
            for (char c : w.toCharArray()) {
                if (!Character.isLetterOrDigit(c)) { alnum = false; break; }
                if (Character.isLetter(c)) {
                    if (V.contains(c)) hv = true; else hc = true;
                }
            }
            if (alnum && hv && hc) cnt++;
        }
        return cnt;
    }
}

#include <string>
#include <sstream>
#include <cctype>
#include <unordered_set>
using namespace std;

int countValidWords(string s) {
 unordered_set<char> V{'a','e','i','o','u','A','E','I','O','U'};
 stringstream ss(s);
 string w;
 int cnt = 0;
 while (ss >> w) {
 if ((int)w.size() < 3) continue;
 bool alnum = true, hv = false, hc = false;
 for (char c : w) {
 if (!isalnum((unsigned char)c)) { alnum = false; break; }
 if (isalpha((unsigned char)c)) {
 if (V.count(c)) hv = true; else hc = true;
 }
 }
 if (alnum && hv && hc) cnt++;
 }
 return cnt;
}

Given a binary string s, find a regex pattern that checks whether the binary number when converted to a decimal number is a power of 2 or not. Locked-in code prints 'True' for each correct match and 'False' for each incorrect match.

A student decides to perform some operations on a big word to compress them so they become easy to remember. An operation consists of choosing a group of K consecutive equal characters and removing them. The student keeps performing this operation as long as it is possible. Determine the final word after the operation is performed.

It can be easily proven that the final word will be unique. Also, it is guaranteed that the final word contains at least one character.

A subsequence is a sequence of characters formed by removing zero or more characters from the string. A substring is a contiguous segment of one or more of a string's characters.

Given two strings x and y, determine the length of the longest subsequence of x that is also a substring of y.

• x = "abcd", y = "abdc" → 3
• x = "hackerranks", y = "hackers" → 7

Rick is trying to create an anti-aging formula, which consists of sequence of different molecules (represented by lowercase alphabets here). The longer the sequence, the more effective the formula. He has been visiting different universes to get samples of the chemical for his experiments. However, due to the struggle between the molecules, the formula becomes unstable if the length of the molecules is more than the tolerance of a molecule in the formula. Each sample is a string of length n, having lowercase alphabetical characters. For each sample, determine the length of the most effective formula. Note: The sequence can be a substring only for that sample. Input Format: The first line contains n, The number of universes. Now for each Universe: The first line contains m, the number of samples. The next line contains a lowercase alphabetical string of length n. The next line contains 26 integers a_j, 1 ≤ a_j ≤ 10³, representing the maximum length of the substring in which each character can exist. Output Format: Print N lines, where each line has an integer stating the length of the longest sequence.

Constraints

• Number of universe n ≤ 10⁵.
• Sample length of each universe, m ≤ 10³.
• The sum of samples in each universe ≤ 10⁶.

In the older days, Douma was an upper moon 6. And as we all know the ability of upper moon 6 was that it doesn't die unless all of its versions are dead. Only Akaza knows how to kill Douma's versions, but as he is the biggest fan of Douma he wouldn't do it, so the demon slayer corps asked Shinobu Kocho to hypnotize him in order to avenge her sister's death. So there is a grid with n rows and m columns where in each cell there is a Douma's version(a demon). The grid is numbered with (0,0) as the top left corner and (n, m) as the bottom right corner. The demons in cells (i + 1, j - 1), (i + 1, j), and (i + 1, j + 1) are called the children of the demon in cell (i, j). And we have a matrix K with n rows and m columns which tells in which turn which cell's demon will be killed by Akaza. So the demon in cell (i,j) will be killed in the K(i,j) th turn. But, if there is a catch, because of Douma's great regenerative abilities, when the demon of cell (i, j) dies, the children demons of this cell get alive anyway were dead at all and similarly the children of demons in cells (i + 1, j - 1), (i + 1, j) and (i + 1, j + 1) also get alive and the process continues. So basically the demon in cell (i,j) dies and the entire sub-tree's demons get alive if any were dead at all. Hashiras are very curious if the given matrix K will be able to kill all the demons or not. Can you help the Hashiras know the state of every cell's demon after Akaza has executed the matrix K. Print a space separated matrix where each cell will be 1 if the demon in that cell will be alive after all operations are executed successfully and 0 otherwise. Note: There is one demon in each cell and all are alive in the beginning. Input Format: First line contains a single integer T which denotes the number of test cases. Then the first line of every test case will contain 2 space separated integers n, m denoting the dimensions of K. Then lines will follow and each line will contain m space separated integers denoting the order of killing. The jth integer of the ith line will tell at what number will the demon of cell (i, j) will be killed. Output Format: For each test case print n lines and each line should have m space separated integers. The jth integer of the ith line will be 1 if the demon at that cell will be alive after executing the killing process as per the order specified in the matrix K or 0 otherwise. Constraints For all test cases

• 1 For test cases worth 20% of total score
• 1 For test cases worth 50% of total score
• 1 For test cases worth 100% of total score
• 1

Constraints

See problem statement above :)

Example 1

Input:

n = 3
m = 3
K = [[2, 1, 3], [4, 7, 8], [6, 9, 5]]

Output:

[[0, 0, 0], [0, 0, 0], [1, 0, 1]]

Explanation: Initially the demon grid will look like this: 1 1 1 1 1 1 1 1 1 And then the demon in the cell (1, 2) gets killed as K(1,2) = 1 looks like this: and all the demons in its subtree will be get alive. So the demon grid looks like this: 1 0 1 1 1 1 1 1 1 And this process continues to achieve the final grid.

Given an array arr of size n (where `n 1 (Avg: 1) | 3 2 (Avg: 2.5) | 1 (Avg: 1) 1 (Avg: 1) | 3 (Avg: 3) | 2 1 (Avg: 1.5) 1 (Avg: 1) | 3 (Avg: 3) | 2 (Avg: 2) | 1 (Avg: 1) In all 3 partitions, the sequence first increases and then decreases.

Constraints

1 -10⁹ ≤ arr[i] ≤ 10⁹`

Example 1

Input:

arr = [1, 3, 2, 1]

Output:

3

Explanation: n/a

Example 2

Input:

arr = [1, 2, 3, 4, 3, 2, 1]

Output:

49

Explanation: n/a

You are given a system that consists of n chains ( C_1, C_2, ..., C_n ). Each chain consists of a sequence of blobs where each blob has a dependency on its parent blob. Each blob of chain ( C_i ) has a corresponding retention time ( B_(i,j) ), where 1Its retention time has passed. None of the other blobs are dependent on it. The admin has decided to organize the system better by merging these chains into a larger, single chain. This is accomplished by introducing dependencies between the first blobs of each chain. Assume there were 3 chains: Some of the possibilities for merging the chains: In the merged structure, no blob's removal should get delayed due to the restructuring. Help admin achieve this by choosing the correct order of links between the chains. **Input Format** N→ number of chains.Nlines of the formc= Chain lengthcspace separated integers = retention times of blobs where blob at index'i'is parent of blob at index'i+1'. Output format Array of integers representing the dependency order of the first blobs of the chains. (A dependency is added from blob at index 'i'to blob at index'i+1'`.

Constraints

• All blobs across the system have a unique retention time.
• Number of chains(n) ≤ 1e5, blobs per chain (m_i)≤1e5
• It's guaranteed that total number of blobs in the system ≤ 3e6

Example 1

Input:

n = 3
retentionTimes = [[3, 4, 5, 8], [3, 2, 3, 1], [3, 6, 7, 9]]

Output:

[3, 1, 2]

Explanation: n/a

By now, you should have realized that Rubrik values your work. But you cannot always perform all your tasks, the hard way. Instead you decide to work smartly. But you soon have a self realization that you lack skills for it, so you hypothesize a task to get an estimate on your smartness. You took a huge number, consisting of n digits. The number may contain leading zeros. You choose to perform the following operation any number of times (possibly zero): You can swap two adjacent digits, if those digits have different parity. Two digits possess different parity, if they have different remainders when divided by 2. You have to find the minimum number you can obtain. The resultant may contain leading zeros. Input Format The first line contains an integer t the number of test cases. Each line of each test case contains a single integer a, of n digits. Output Format For each test case, print a line with the minimum integer you can obtain.

Constraints

• 1 ≤ t ≤ 10⁴
• 1 ≤ n ≤ 10⁵
• The sum of n across all test cases ≤ 10¹⁵

Example 1

Input:

a = "4321"

Output:

3142

Explanation: By swapping the first and second digits, the number becomes 3421. Then, by swapping the second and third digits, it becomes 3241. Finally, by swapping the third and fourth digits, it becomes 3142, which is the minimum number that can be obtained.

The presented problem involves an astral constellation, depicted as an array of n integers where each representing the luminosity of a star. The beauty of this constellation is determined by the maximum overall sum of luminance of any consecutive light cluster. It could range from none of the stars to all the stars of the constellation. Bear in mind an example of a constellation represented by the array [20, -9, 0, 4, 0] the beauty of this constellation is 21. On the other hand, a constellation represented by [-3, -5, -1, -4] has a beauty of 0 units. Assume that you are equipped with a cosmic amplifier, having a power multiplier of z. This device allows you to magnify the luminescence of any chosen segment within the constellation by a factor of z. Here comes the challenge: You can use this amplification at most once, so the task is to decipher how to maximize the beauty constellation after this amplification procedure. Function Description Complete the function enhanceLuminescence. enhanceLuminescence has the following parameters:

• int arr[n]: represents the individual luminescence of each celestial entity within the constellation.
• int z: the power multiplier that can be applied to a chosen sequence within the constellation. Returns int: the maximum possible beauty of the arrangement after applying the amplification.

Constraints

• The size of the stars array, n, lies in the range of 1 ≤ n ≤ 2 * 10⁵.
• The elements of the stars array, a1, a2, a3, ..., lie in the range 10⁻⁹ ≤ ai ≤ 10⁹.
• The amplification power, z, lies in the range -100 ≤ z ≤ 100.

Example 1

Input:

arr = [3, 2]
z = 2

Output:

10

Explanation: For the constellation [3, 2], if we apply a power multiplier of 2 to the entire constellation, we get an amplified luminescence of [6, 4] and a beauty of 10.

Example 2

Input:

arr = [-5, -9, -2, 1, -6]
z = -3

Output:

30

Explanation: Here we multiply the last [-2, 1, -6] with the magnification factor. The final magnified array looks like [-5, -9, 6, -3, 18]. Hence the beauty of this arrangement is the sum of [9, 6, -3, 18] which is 30.

Example 3

Input:

arr = [1, 2, 4, 5]
z = -2

Output:

12

Explanation: Here all the elements in the array are positive hence we do not apply the magnification and the beauty of the arrangement is the sum of [1, 2, 4, 5] which is 12.

The developers are trying to optimize their horizontal pod autoscaler for their micro-services. There are n micro-services where the number of pods for the ith micro-service is pods[i]. According to traffic, the number of pods of a service can increase or decrease. Also, at specific times when there is expected traffic, all services with fewer than x pods are assigned x pods. There is an event log of size m, which is described as a 2D array logs where logs[i] is an array of integers of size = 3. The interpretation of these logs are shown. [1, p, x]: the number of pods of the p^th micro-service is changed to x (1 [2, -1, x]: all the micro-services whose number of pods is less than x are changed to x. Find the resulting number of pods for the micro-services. Function Description Complete the function findPodCount in the editor below. findPodCount has the following parameters:

• 1. int pods[n]: the number of pods for the micro-services
• 2. int logs[m][3]: the event log of the horizontal pod autoscaler Returns int[n]: the # element represents the final pod count of the mth micro-service

John and Mary, good friends, play a game to see how strong their friendship is. John gives Mary a tricky puzzle to solve. Here's how it goes: Given a string s consisting of digits from 0 to 9 inclusive, You can choose a position i and delete a digit d on the ith position. Then Insert the digit min (d+1, 9) in any position (at the beginning, at the end or in between any two adjacent digits. What is the lexicographically smallest string you can get by performing these operations? A string 'a' is lexicographically smaller than a string 'b' of the same length of and only if the following holds: In the first position where a and b differ, the string 'a' has a smaller digit than the corresponding digit. Help Mary prove her friendship by solving the puzzle. Input Format The first line contains a single integer t -- the number of test cases. Then the test cases follow. Each test case consists of a single line that contains one string s. the string consisting of digits. Please note that s is just a string consisting of digits, so leading zeros are allowed. Output Format Print a single string the lexicographically smallest string that is possible to obtain.

Constraints

• 1 ≤ t ≤ 1e4
• 1 ≤ |s| ≤ 2 * 1e5
• It's guaranteed that the sum of lengths of s

Example 1

Input:

s = "415863388791991"

Output:

"111334567888999"

Explanation: By performing the operations as per the rules, the lexicographically smallest string that can be obtained is "111334567888999".

Given two arrays change and arr that consist of n and m integers respectively. In the ith operation, one of the two operations can be performed: you can choose to decrement any element of arr by 1 or do nothing. if change[i] > 0 and arr[change[i]] = 0, it can be changed to NULL. Assume indexing starts from 1, find the minimum number of operations required to change all the elements of the array to NULL or report -1 if it is not possible. Function Description Complete the function getMinOperations in the editor below. getMinOperations has the following parameter(s):

• int change[n]: an array of integers
• int arr[m]: an array of integers Returns int: the minimum number of operations required to change all the elements to NULL, or -1 if it is not possible

Constraints

:o

The cost of a stock on each day is given in an array, arr. An investor wants to buy the stocks in triplets such that the sum of the cost for three days is divisible by d. The goal is to find the number of distinct triplets (i, j, k) such that i Function Description Complete the function getTripletCountin the editor below. The function must return an integer denoting the total number of distinct triplets.getTripletCount` has the following parameters:

• int arr[n]: an array of integers
• int d: the divisor

Constraints

• 3 ≤ n ≤ 10³
• 1 ≤ arr[i] ≤ 10⁹
• 2 ≤ d ≤ 10⁶

Example 1

Input:

arr = [3, 3, 4, 7, 8]
d = 5

Output:

3

Explanation: The triplets whose sum is divisible by d are shown.

• Triplet with indices - (0, 1, 2), sum = 3+3+4 = 10
• Triplet with indices - (0, 2, 4), sum = 3+4+8 = 15
• Triplet with indices - (1, 2, 4), sum = 3+4+8 = 15 Hence, the answer is 3.

A quick note: I changed the input 'operations' to a 2D String array to accommodate the 'Re' and 'Ro' entries. Other than this modification, the question should match the original prompt about 98% You are given an initial key tree. A level is the number of parent keys corresponding to a given key of the key tree. Initial values of keys are 0. Example: Key 1 with value X1 would be at level 0. Key 2, Key 3 at level 1, and so on. There is a sequence of Rotation and Rekey operations that can happen: Rotation: Ro p v means that a new key (v) needs to be added to parent p. Initial value is 0, though referred to as X_v in the figure. Rekey: Re I z means that for a level (I) and the number (z) to update the value of all the keys on the same level and their subsequent children until the leaves. The new value would be the previous value of the key + z. For Example: Ro 1 9 would give us: Ro 1 4 would give us: Given an initial tree with n nodes and q operations sequence of Ro and Re operations, find the sum of values for all the keys.

Constraints

• 1 ≤ n, q ≤ 10⁵
• 1 ≤ z ≤ 10⁵, where z is the number added in the Rekey query.
• All other inputs satisfy the constraints and problem requirements.
• In the Rotation query, the new key v always equals the current number of nodes in the tree + 1.

Example 1

Input:

operations = [["1", "2"], ["2", "4"], ["1", "3"], ["4", "5"], ["Re", "1", "10"], ["Ro", "4", "6"], ["Re", "2", "4"], ["Re", "3", "4"]]
n = 5
q = 4

Output:

70

Explanation: n/a

Example 2

Input:

operations = [["2", "1"], ["3", "1"], ["4", "2"], ["5", "1"], ["Ro", "4", "6"], ["Re", "2", "91277"], ["Re", "1", "50944"], ["Ro", "1", "7"], ["Re", "1", "17666"]]
n = 5
q = 5

Output:

3607116

Explanation: n/a

In an outsourcing company, Employees are outsourced to clients and paid for their work. In this company, every employee (except for the CEO) has a RM (Reporting Manager). Any employee takes task assignment only from their RM or RM's RM and so on. Each employee has a fixed cost and a Leadership level. You are a consultant tasked with selecting employees for a client. Each selected employee is to be paid a cost fixed for them. The total amount of cost to hire them should be within a budget. To make sure that Employees complete the client's work you choose a Manager, who is an employee that can assign tasks to all selected employees. The Manager may or may not be a selected employee, if he is not then he is not paid for. You need to maximize the happiness level of the Client while making sure the cost is within a budget. The happiness of client is the equal to (Leadership level of the Manager * number of employees hired). The following figure represents the company where each node is an employee and contains data (i, cost, leadership). The RM to employee relationship is represented by arrows. Let's say, Budget is 20. The Client satisfication is maximum at 1200 when 2, 6, 7, or 4, 6, 7 are hired with 1 as the Manager in either case. Input Format You will process input from stdin. The first line contains an integer T, the number of testcases. T testcases follow. For each testcase, first line contains two numbers N, the number of employees and M, the budget. N lines follow, each line representing R[i], C[i], L[i] for ith employee (i starts from 1) denoting RM, cost and leadership respectively.

Constraints

• 1 ≤ T ≤ 10
• 1 ≤ N ≤100 000 The number of Employees
• 1 ≤ M ≤1 000 000 000 The budget
• 0 ≤ R[i] < i The RM for each employee
• 1 ≤ C[i] ≤ M The amount of cost of each employee
• 1 ≤ L[i] ≤ 1 000 000 000 The leadership level of each employee
• Subtask 1: N ≤ 10
• Subtask 2: N ≤ 3000
• Subtask 3: Original

Example 1

Input:

employeeData = [[2, 10, 400], [1, 10, 300], [2, 15, 100], [1, 10, 60], [2, 5, 800], [2, 5, 100], [2, 5, 100]]
budget = 20

Output:

1200

Explanation: The Client satisfaction is maximum at 1200 when 2,6,7 or 4,6,7 are hired with 1 as the Manager in either case.

In an interstellar civilisation, symbolised by a connected, undirected graph of n celestial bodies and m cosmic pathways. Each celestial body represents an alien entity, and each cosmic pathway (i, j) signifies an alliance between alien entities i and j. In this cosmic civilisation, entity i harnesses an energy level e_i. Alien entity j feels eclipsed by entity i if e_j equals e_i + 1, implying entity j possesses exactly one more unit of energy than entity i. The civilisation is termed as having a stellar gradient if in every allied pair, one entity feels eclipsed by the other. For some alliances, it's known which entity feels eclipsed by its ally. However, the direction of the eclipse remains unknown for the rest. The energy disparity in this civilisation is defined as min e_i - max e_j 1 ≤ i ≤ n 1 ≤ j ≤ n It's impossible for this civilisation to exhibit this stellar gradient with the known data, such a situation should be reported. Otherwise, a distribution of energy that fulfils the conditions for a stellar gradient should be determined and within this structure, energy disparity should be maximised. Answer the maximum stellar gradient possible for the planet system. If no such configuration possible return -1.

Constraints

• The number of planets, 1 ≤ n ≤ 200
• The number of cosmic pathways, 1 ≤ m ≤ 2000

On a planet lying on the brink of the Milky Way, called AFWP-700, there is a very rare type of gem. This gem has magical properties. This gem is very expensive but it affects the person carrying it. Depending on the potency of the collected gem, it may boost a person's stamina or reduce it. Mike, a researcher on planet AFWP-700 must navigate through the planet's tough terrain in a certain path from Base A to Base B. On the way, he must collect at most n gems in the given order and then reach Base B. Mike must go through the path and if he encounters a gem, he must either pick it up or destroy it (to avoid being affected by it). Having researched the different potencies of the gem, a numerical value is known for the potency of the gems. Mike must keep his potency non-negative throughout the trip. Output the maximum number of gems that Mike can collect. Input Format for Custom Testing The first line contains an integer n, the total gems along the path. The next line contains n space separated integers (a_i for all 1 ≤ i ≤ n). Output Format A single integer containing the maximum number of gems that Mike can collect without having negative stamina at any point.

Constraints

1 ≤ n ≤ 10⁵ -10⁹ ≤ a_i ≤ 10⁹

On one of their infamous adventures, Morty ends up in a dangerous situation again. Luckily, Rick is able to save him using one of his gizmos. To return the favor, Morty decides to gift Megaseeds to Rick. He decides to prepares num number of crates holding the seeds, numbered from 0 to num - 1. In the beginning, each crate K contains c_K number of Megaseeds. It is perfectly acceptable if some of the crates are empty. However, Morty, being the nice guy, plans to include at least one non-empty crate. Rick, being the eccentric character, will only accept the gift if the number of seeds in each crate is multiple of an integer div where div > 1. Summer joins Morty's plan and starts helping him out by redistributing the seeds to fit Rick's criteria. She can move a seed from crate i to either the preceding crate (if it exists) or to the crates after it (if they exist). Both Morty and Summer wish to complete this as soon as possible. Your task is to return the minimum number of operations that Summer needs to perform so that the gift meets Rick's criteria. If the gift cannot be modified to meet Rick's standards, return -1. Input Format

• The first line contains an integer num, the number of crates.
• The second line contains num integers, representing the initial number of seeds in each crate. Output Format Return the minimum number of operations required. If it is impossible to meet the criteria, return -1.

Constraints

• The number of crates, 1 ≤ num ≤ 10⁶.
• The initial number of seeds in each crate, 0 ≤ seeds[i] ≤ 10⁶.
• Out of seeds[0], seeds[1], seeds[2], ..., seeds[num-1], at least one is assured to be greater than 0.

Cooper is stuck in the 5th dimension with TARS. They have to find a way to transmit gravitational data to Murph so that she can solve Dr. Brand's equation to harness gravity. The higher dimensional beings agreed to help them out, but only if they are able to solve a task for them. Cooper and TARS are presented with n rocks. Each rock has a mass attached to it (m1, m2, m3, m4, . . . mn). They can perform two types of operations on this ordered set of rocks:

• Given two indexes x and y, find the total mass of the rocks with indices in the range x to y, i.e, m_x + m_x+1 + ... + m_y and print it.
• They are also presented with a machine capable of altering the mass of any rock. Presented again with two indexes x and y, and a number z, alter the masses of the rocks with indices in the range x to y such that m_i (x They have been asked to perform ops number of operations, where each operation can either be of the type 1 or 2. Input Format and Constraints
• An integer n, denoting the number of rocks. 1 ≤ n ≤ 10⁵.
• The second line contains n integers denoting the initial masses of the rocks. 0 ≤ m[i] ≤ 10⁶.
• The third line contains the number of operations, ops, to be performed on the rocks. 1 ≤ ops ≤ 5*10⁴.
• The above is followed by ops number of lines, where each line consists of:
• An integer type, which is either 1 or 2, denoting the operation performed.
• If type is 1, it is followed by two integers, s and e, denoting the range for which total mass is to be calculated. 1 ≤ s ≤ e ≤ n.
• If type is 2, it is followed by three integers, s, e, and z. z is the number using which the mass of the rocks in the range s to e is to be altered using ^ which is the xor operation. 1 ≤ s ≤ e ≤ n and 1 ≤ z ≤ 10⁶. The changes made in this query persist for all future operations as well.

Example 1

Input:

n = 4
masses = [1, 5, 2, 4]
ops = 3
queries = [[1, 1, 4], [2, 2, 3, 4], [1, 1, 4]]

Output:

[12, 12]

Explanation:

• In the first query of type 1, the sum of masses of rocks in the range 1 to 4 is asked for, hence 12 is printed.
• In the second query of type 2, the masses of rocks in the range 2 to 3 is modified by performing xor with 4. The new array becomes → 1 1 6 4.
• In the third query of type 1, the masses of rocks in the range 1 to 4 is asked for, hence, 12 is printed.

Example 2

Input:

n = 5
masses = [10, 6, 1, 9, 2]
ops = 3
queries = [[1, 1, 5], [2, 1, 3, 8], [1, 2, 4]]

Output:

[28, 32]

Explanation:

• In the first query of type 1, the sum of masses of rocks in the range 1 to 5 is asked for, hence 28 is printed.
• In the second query of type 2, the masses of rocks in the range 1 to 3 is modified by performing xor with 8. The new array becomes → 2 14 9 9 2.
• In the third query of type 1, the masses of rocks in the range 2 to 4 is asked for, hence, 32 is printed.

宇宙之间形成一棵以节点 1 为根的树(节点 2..n 的父亲由 p 给出)。第 i 个宇宙有 evilness e[i]。Hero 有一把能量为 m 的枪。每次"开枪"会摧毁一个子树并消除其总 evilness。一个子树被允许保留的条件是其总 evilness < k。求最少开枪次数让全树合法(或将所有节点摧毁)。

Constraints

• Number of universes, n ≤ 10⁵
• The power of the gun, m ≤ 10⁵
• The evilness of each universe and total evilness, K ≤ 10¹⁸

Example 1

Input:

n = 6
m = 3
k = 100
e = [1, 100, 1, 1, 1, 1]
p = [1, 1, 2, 3, 3]

Output:

4

Explanation:

While on his crazy adventures, Rick and Morty stumbled upon an alien species called the Oracles, known for their great mathematical prowess. Among the Oracles was a game called the Oracle, which they taught their infants and toddlers. In this game, there is one dealer and one player (the infant). The dealer deals the player an initially empty array A. The dealer then has the ability to perform two kinds of operations on the list: Append any number x to the end of the array. Copy the array x times back-to-back to A. The dealer performs an operation but does not reveal the array's content to the player. The Oracle then rapidly asks the player what numbers are present at different indices of the array. Rick thinks the problem is in P, but is it? Help him solve this problem. Input Format The first line contains two integers n and q, where n denotes the number of operations the dealer performs, and q denotes the number of queries the dealer asks the player. The next n lines each contain two space-separated integers. The i-th line (1

• The following line contains q space-separated integers, q_j (1 Output Format Print q integers, each representing the value at the queried index of the array.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ q ≤ 10⁵
• b_i belongs to {1, 2}, for all i (1 ≤ i ≤ n)
• 1 ≤ x_i ≤ n for b_i = 1
• 1 ≤ x_i ≤ 10⁹ if b_i = 2
• 1 ≤ q_j ≤ min(10¹⁸, e) for all j (1 ≤ j ≤ q), where e is the final size of the array.

Example 1

Input:

n = 5
q = 10
operations = [[1, 5], [1, 2], [2, 1], [1, 3], [2, 1]]
queries = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Output:

[5, 2, 5, 2, 3, 5, 2, 5, 2, 3]

Explanation:

• Before the first operation: A = []
• After the first operation: A = [5]
• After the second operation: A = [5, 5]
• After the third operation: A = [5, 5, 2, 2]
• After the fourth operation: A = [5, 5, 2, 2, 5, 5, 2, 2]
• After the fifth operation: A = [5, 5, 2, 2, 5, 3, 5, 2, 5, 2, 3]

Given n strings (consisting of lowercase english letters), each of length m, the Blobstore team at Rubrik is considering introducing a deduplication feature to save space when storing these strings on disk. Your task is to help them maximize these space savings with the following method: A block is defined as a contiguous, non-overlapping substring of a string. The length of a block, l, divides each string into several blocks, with the last block possibly having a length of < l. For a block b in string s_i, if an identical block b' exists anywhere within the previous or the same string (i.e., string i-1 or i), then b can be deduplicated to b'. In other words, instead of storing the content of block b, we store a reference to previously stored b', saving storage space. For this problem, we will assume that a reference does not take any space. The goal is to find the ideal block size l that maximizes the storage savings. However, l must not be smaller than a provided threshold k. You should print the ideal block size and the corresponding storage savings in terms of the number of characters saved. If there are multiple block sizes which yield the maximum savings, return the smallest such block size. Example - Consider the below 3 string: aandy ndaax bendx If the block length is 2, then strings will be divided into blocks in the following manner: aa nd y nd aa x bc nd x And they can be stored as the following after deduplication process - aa nd y -- x bc __ Because of the deduplication, we need not write 7 characters, so we saved 7 character writes. Function Description Complete the function unalignedDedupe in the editor. unalignedDedupe has the following parameters:

• 1. String[] strings: an array of strings
• 2. int m: the length of each string
• 3. int k: the minimum block size Returns int[]: an array of two integers where the first integer is the ideal block size and the second integer is the corresponding storage savings

Constraints

• 1 ≤ n ≤ 1.5 * 10⁶
• 1 ≤ m ≤ 1.5 * 10⁶
• 1 ≤ n*m ≤ 1.5 * 10⁶
• 1 ≤ k ≤ m

Example 1

Input:

strings = ["aand", "adaa", "bend"]
m = 4
k = 1

Output:

[1, 7]

Explanation: n/a

Example 2

Input:

strings = ["abcdef", "defbac", "abdefa"]
m = 6
k = 2

Output:

[3, 6]

Explanation: n/a