// 未提交验证
import java.util.*;

public class LivingInTree {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }

        // 从上往下找一条路径的最大值，那么需要全部遍历完呀肯定
        dfs(nums, n, nums[0], 1); // nums[0]，根节点，使其对应的k为1

        System.out.println(ans);
    }

    static int ans = 0;
    public static void dfs(int[] nums, int n, int sum, int k) {
        if (k * 2 + 1 > n) {  // 表明已经是叶子节点，左右孩子都没有
            ans = Math.max(ans, sum);
            return;
        }

        // 只要有一个，那都要往下递归的
        if (k * 2 <= n) {
            dfs(nums, n, sum + nums[k * 2 - 1], k * 2);
        } // 不确定要不要写else，就是sum不便放进去的
        if (k * 2 + 1 <= n) {
            dfs(nums, n, sum + nums[k * 2], k * 2 + 1);
        } // 不确定要不要写else，就是sum不便放进去的
    }
}


// 有些解法使用层序
public class Main
{
    public static void main(String args[])
    {
        Scanner cin = new Scanner(System.in);
        int n =  Integer.parseInt(cin.nextLine());
        String[] _nums = cin.nextLine().split(" ");
        int[] nums = new int[n + 1];
        for (int i = 1; i <= n; i++) nums[i] = Integer.parseInt(_nums[i - 1]);
        int ans = 0;
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(1);
        while (!q.isEmpty()) {
            int t = q.poll();
            ans = Math.max(ans, nums[t]);
            if (2 * t <= n){
                nums[2 * t] += nums[t];
                q.offer(2 * t);
            }
            if (2 * t + 1 <= n) {
                nums[2 * t + 1] += nums[t];
                q.offer(2 * t + 1);
            }
        }
        System.out.println(ans);
    }
}
// vx公众号关注TechGuide 实时题库 闪电速递

import java.util.Scanner;

public class TreeMaxSum {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        TreeNode[] treeNodes = new TreeNode[n];
        TreeNode root = null;

        for (int i = 0; i < n; i++) {
            treeNodes[i] = new TreeNode(scanner.nextInt());
        }

        for (int i = 0; i < n; i++) {
            // 0是跟节点，此处左右子树都可以，所以相比而言，还是缺少了一些东西的
            int parentIndex = scanner.nextInt();
            if (parentIndex == 0) {
                root = treeNodes[i];
            } else {
                // 左边不空的话先放左边
                // 注意0代表是根，1代表第0个节点
                if (treeNodes[parentIndex-1].left == null) {
                    treeNodes[parentIndex-1].left = treeNodes[i];
                } else {
                    treeNodes[parentIndex-1].right = treeNodes[i];
                }
            }
        }

        dfs(root);

        System.out.println(ans);
    }

    static int ans = Integer.MIN_VALUE;
    /**
     * 考虑
     * @return
     */
    public static int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }

        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftGain = Math.max(dfs(node.left), 0);
        int rightGain = Math.max(dfs(node.right), 0);


        ans = Math.max(leftGain + rightGain + node.val, ans);

        return Math.max(leftGain + node.val, rightGain + node.val);
    }
}

// 此处使用队列，进行模拟
import java.util.*;
import java.util.stream.Collectors;

public class TemplateLianBiao {
    // 打表测试
    // 5个组两两比较，一共可以比赛十个场次
    public static Deque<int[]> queue = new ArrayDeque<>();

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int[] scores = new int[5];
        for (int i = 0; i < 5; i++) {
            scores[i] = in.nextInt();
        }
        Set<List<Integer>> set = new HashSet<>();

        queue.offerLast(new int[]{0, 0, 0, 0, 0});
        // 0与其余比较
        for (int i = 0; i < 5; i++) {
            for (int j = i+1; j < 5; j++) {
                int size = queue.size();
                for (int k = 0; k < size; k++) {
                    int[] temp = queue.pollFirst();
                    temp[i] += 3;
                    temp[j] += 0;
                    queue.offerLast(temp.clone());
                    temp[i] -= 3;
                    temp[j] -= 0;
                    temp[i] += 1;
                    temp[j] += 1;
                    queue.offerLast(temp.clone());
                    temp[i] -= 1;
                    temp[j] -= 1;
                    temp[i] += 0;
                    temp[j] += 3;
                    queue.offerLast(temp.clone());
                }
            }
        }

        while (!queue.isEmpty()) {
            int[] temp = queue.pollFirst();

            Arrays.sort(temp);
            for (int i = 0; i < 2; i++) {
                int temoInt = temp[i];
                temp[i] = temp[4-i];
                temp[4-i] = temoInt;
            }
            set.add(Arrays.asList(temp[0], temp[1], temp[2], temp[3], temp[4]));
        }
        
        System.out.print(a == set.size() ? "yes" : "no");
        System.out.print(set.contains(Arrays.asList(scores[0], scores[1], scores[2], scores[3], scores[4])) ? " yes" : " no");
    }
}

// 未验证
import java.util.*;

// [[0,1,1,1],[0,0,0,1],[1,0,8,1],[1,0,1,1]]
// 一个方阵，有0可通行，1阻碍，8建议
// 可从边缘的任意地方进去得到奖励，然后找出步数最少的路径
// 若一样，一个即可

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] strs = scanner.nextLine().split("\\],\\[");
        strs[0] = strs[0].substring(2, strs[0].length());
        strs[n-1] = strs[n-1].substring(0, strs[n-1].length()-2);

        int[][] g = new int[n][n];
        for (int i = 0; i < n; i++) {
            g[i] = Arrays.stream(strs[i].split(",")).mapToInt(Integer::valueOf).toArray();
        }


        for (int i = 0; i < n; i++) {
            System.out.println(Arrays.toString(g[i]));
        }

        for (int i = 0; i < n; i++) {
            if (g[i][0] == 0) {
                boolean[][] visited = new boolean[n][n];
                visited[i][0] = true;
                List<int[]> list = new ArrayList<>();
                list.add(new int[]{i, 0});

                dfs(g, new int[]{i, 0}, list, visited);
            }
            if (g[n-1][0] == 0) {
                boolean[][] visited = new boolean[n][n];
                visited[n-1][0] = true;
                List<int[]> list = new ArrayList<>();
                list.add(new int[]{n-1, 0});

                dfs(g, new int[]{n-1, 0}, list, visited);
            }
        }

        for (int i = 1; i < n; i++) {
            if (g[0][i] == 0) {
                boolean[][] visited = new boolean[n][n];
                visited[0][i] = true;
                List<int[]> list = new ArrayList<>();
                list.add(new int[]{0, i});

                dfs(g, new int[]{0, i}, list, visited);
            }
            if (g[n-1][i] == 0) {
                boolean[][] visited = new boolean[n][n];
                visited[n-1][i] = true;
                List<int[]> list = new ArrayList<>();
                list.add(new int[]{n-1, i});

                dfs(g, new int[]{n-1, i}, list, new boolean[n][n]);
            }
        }

        System.out.print("[");
        for (int i = 0; i < minPath.size()-1; i++) {
            int[] temp = minPath.get(i);
            System.out.print("(" + temp[0] + "," + temp[1] + "),");
        }
        System.out.print("(" + minPath.get(minPath.size()-1)[0] + "," +  minPath.get(minPath.size()-1)[1] + ")" + "]");
    }


    /**
     * 深度 + 回溯，算带有路径的好算一点
     * @param g
     * @param curIndex
     * @param path
     */
    static int n = 4;
    static int minPathCount = Integer.MAX_VALUE;
    static List<int[]> minPath;
    static int[][] dir = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public static void dfs(int[][] g, int[] curIndex, List<int[]> path, boolean[][] visited) {
        int x = curIndex[0], y = curIndex[1];
        if (g[x][y] == 8) {
            if (minPathCount > path.size()) {
                minPathCount = path.size();
                minPath = new ArrayList<>(path);
            }
            return;
        }
        if (path.size() > minPathCount) {
            return;
        }

        for (int i = 0; i < n; i++) {
            int newX = x + dir[i][0], newY = y + dir[i][1];
            if (newX >= 0 && newX < n && newY >= 0 && newY < n && !visited[newX][newY] && g[newX][newY] != 1) {
                visited[newX][newY] = true;
                path.add(new int[]{newX, newY});

                dfs(g, new int[]{newX, newY}, path, visited);

                visited[newX][newY] = false;
                path.remove(path.size() - 1);
            }
        }
    }
}

import java.util.List;
import java.util.Scanner;

// 题解
class ListNode{
    long val;
    ListNode next;
    public  ListNode(long val, ListNode next){
        this.val = val;
        this.next = next;
    }
}

public class TechGuide{

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int root = 0;
        int n = sc.nextInt();
        System.out.println(n);
        int color[] = new int[n];
        ListNode[] Graph = new ListNode[n];
        for (int i = 0; i < n; i++) {
            Graph[i] = new ListNode(0,null);
        }
        sc.nextLine();
        String str = sc.nextLine();
        System.out.println(str);
        for (int i = 0; i < n; i++) {
            if(str.charAt(i)=='R'){
                color[i] = 1;
            }
        }
        for (int i = 0; i < n-1; i++) {
            int u = sc.nextInt()-1;
            int v = sc.nextInt()-1;
            insert(u,v,Graph);
        }
        int visited[] = new int[n];
        dfs(root,visited,0,0,color,Graph);
        long ans = 0;
        for (int i = 0; i < n; i++) {
            ans+=Graph[i].val;
        }
        System.out.println(ans);
    }


    public static void insert(int u,int v,ListNode[] G){
        ListNode vNode = new ListNode(v,G[u].next);
        G[u].next = vNode;
        ListNode uNode = new ListNode(u,G[v].next);
        G[v].next = uNode;
    }

    public static void dfs(int root,int[] visited,int red,int blue,int color[],ListNode[] G){
        visited[root] = 1;
        if(color[root]==1) red++;
        else blue++;
        G[root].val = Math.abs(red-blue);
        ListNode p = G[root].next;
        while(p!=null){
            if(visited[(int)p.val]!=1){
                dfs((int)p.val,visited,red,blue,color,G);
            }
            p = p.next;
        }
        visited[root] = 0;
    }
}
// 微信公众号关注TechGuide 实时题库 闪电速递


// ######################################*######################################
// 自己做的
package org.jcwang.zoom;

import java.util.*;

/**
 * 建树 + dfs
 * 树节点染色体计算总体权重
 * 使用邻接表，使用数组 + 链表，注意因为这个节点只有一个值，所以都不用创建节点了，那个值直接在list里面的元素表示就好
 * 好吧，是需要创建的，因为节点的值需要存的是当前节点的编号，就是在graph数组中是第几个的意思
 */
public class Main2 {
    private static class ListNode {
        long num;
        boolean isRed;

        public ListNode(long num, boolean isRed) {
            this.num = num;
            this.isRed = isRed;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        List<ListNode>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }

        boolean[] color = new boolean[n];
        String str = scanner.next();     // 注意此处如果使用nextline的话需要前面先读取nextLine一次
        for (int i = 0; i < n; i++) {
            color[i] = str.charAt(i) == 'R';
        }

        for (int i = 0; i < n-1; i++) { // n-1条线，建树
            int a = scanner.nextInt() - 1;
            int b = scanner.nextInt() - 1;
            // 由于不知道那个是父亲，所以当作无向图都存储一遍，后面遍历子节点的时候需要用标记父亲节点，来避免遍历父亲，而不是回溯的意思吧？
            graph[a].add(new ListNode(b, color[b]));  // 如果是存放节点的话，此处应该是加入新创建的节点
            graph[b].add(new ListNode(a, color[a]));
        }

        boolean[] visited = new boolean[n];
        System.out.println("访问顺序：" + 0);
        dfs(graph, new ListNode(0, color[0]), 0, 0, visited);
        System.out.println(ans);
    }

    static int ans = 0;
    /**
     * dfs遍历，求每一个节点的染色体差，然后相加
     * @param graph
     * @param curNode 如果是节点的话，这个值应该是节点的引用
     */
    public static void dfs(List<ListNode>[] graph, ListNode curNode, int red, int blue, boolean[] visited) {
        // 标记父节点，以便不至于访问字节点的时候有访问到，因为是按照邻居节点存的
        // 即访问了该节点，其他的节点访问的时候不能访问了
        visited[(int)curNode.num] = true;

        if (curNode.isRed) {
            red += 1;
        } else {
            blue += 1;
        }
        ans += Math.abs(red - blue);

        for (ListNode listNode: graph[(int)curNode.num]) {
            // 就是等会儿访问该子节点的邻居节点，可能是该子节点的父亲节点，需要剔除
            if (!visited[(int)listNode.num]) {
                System.out.println("访问顺序：" + listNode.num);
                dfs(graph, listNode, red, blue, visited);
            }
        }

        // 该节点到此结束了，后面该节点又能被访问了
        visited[(int)curNode.num] = false;
    }
}

// 没有放入检验
package org.jcwang.zoom;

import java.util.*;

public class GuPiao {
    public static void main(String[] args) {
        Solution solution = new GuPiao().new Solution();
        solution.tuijian();
    }

    class Solution {
        // 并查集参数
        int N = 500001;
        int[] parent = new int[N];
        int[] rank = new int[N]; // 判断该联通的深度
        int size[] = new int[N]; // 题目中需要，判断这个联通的有多少个个数

        // 并查集：查找
        int find(int x) {
            // 若自己等于自己，证明是根
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }

            return parent[x];
        }

        // 并查集：查询
        boolean query(int a, int b) {
            return (parent[find(a)] == parent[find(b)]);
        }

        // 并查集：融合
        // 此处用rank加了优化
        void union(int a, int b) {
            int rootA = find(a);
            int rootB = find(b);

            if (rank[rootA] > rank[rootB]) {
                // 让深度小的当作根
                int temp = rootA;
                rootA = rootB;
                rootB = temp;
            }

            parent[rootB] = rootA;
            size[rootA] += size[rootB];
            if (rank[rootA] == rank[rootB]) {
                rank[rootA] += 1;   // 根的深度+1
            }
        }

        int index = 0;    //  给股票编号，放入并查集


        void tuijian() {
            // 并查集初始化
            for (int i = 0; i < N; i++) {
                parent[i] = i;
                rank[i] = 0;    // 一开始0还是1无伤大雅？只要判断大小就行了
                size[i] = 1;
            }

            Map<String, Integer> nameStockIndexMap = new HashMap<>();
            Map<String, Integer> stockStockIndexMap = new HashMap<>();
            Map<String, Integer> nameStockNumMap = new HashMap<>();

            Scanner scanner = new Scanner(System.in);
            int n = scanner.nextInt();

            while (n-- != 0) {
                int op = scanner.nextInt();
                switch (op)  {
                    case 1: // 加入股票
                        String name = scanner.next();
                        int stockNum = scanner.nextInt();
                        int firstStock = -1;

                        for (int i = 0; i < stockNum; i++) {
                            String stockName = scanner.next();
                            int curStockIndex = -1;
                            // 股票有编号，则取出，没有编号，那么新建
                            if (stockStockIndexMap.containsKey(stockName)) {
                                curStockIndex = stockStockIndexMap.get(stockName);
                            } else {
                                curStockIndex = index++;

                            }
                            stockStockIndexMap.put(stockName, curStockIndex);
                            nameStockIndexMap.put(name, curStockIndex);
                            nameStockNumMap.put(name, stockNum);

                            if (i == 0) {
                                firstStock = curStockIndex;
                            } else {
                                // 将后面的stock融合到第一张去
                                // 需要判断，股票不联通的时候才融合
                                if (!query(curStockIndex, firstStock)) {
                                    union(curStockIndex, firstStock);
                                }
                            }
                        }
                        break;
                    case 2:
                        String name2 = scanner.next();
                        if (!nameStockIndexMap.containsKey(name2)) {
                            System.out.println("error");
                        } else {
                            System.out.println(size[find(nameStockIndexMap.get(name2))] - nameStockNumMap.get(name2));
                        }
                        break;
                    default:
                        break;
                }
            }
        }
    }
}

public class Main
{
    public static void main(String args[])
    {
        Scanner cin = new Scanner(System.in);
        int n =  Integer.parseInt(cin.nextLine());
        int[] card = Arrays.stream(cin.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();
        int[] origin = new int[n];
        Deque<Integer> d = new ArrayDeque<>();
        for (int i = 0; i < n; i++) d.offerLast(n - i - 1);
        for (int i = 0; i < n; i++) {
            d.offerFirst(d.pollLast());
            d.offerFirst(d.pollLast());
            origin[d.pollLast()] = card[i];
        }
        for (int i = 0; i < n; i++) {
            System.out.printf("%d ", origin[i]);
        }
    }
}
// vx公众号关注TechGuide 实时题库 闪电速递

public class Main
{
    public static void main(String args[])
    {
        Scanner cin = new Scanner(System.in);
        int n =  Integer.parseInt(cin.nextLine());
        int[] nums = Arrays.stream(cin.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();
        long count = 0;
        Map<Integer, Integer> mp = new HashMap<>();
        mp.put(nums[n - 1], 1);
        for (int i = n - 2; i >= 1; i--) {
            for (int j = i - 1; j >= 0; j--) {
                count += mp.getOrDefault(3 * nums[i] - nums[j], 0);
            }
            mp.put(nums[i], mp.getOrDefault(nums[i], 0) + 1);
        }
        System.out.println(count);
    }
}
// vx公众号关注TechGuide 实时题库 闪电速递

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

int main() {
    freopen("test.txt", "r", stdin);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < m; ++i) {
        cin >> b[i];
    }
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i < n + 1; ++i) {
        dp[i][0] = dp[i - 1][0] + abs(a[i - 1]);
    }
    for (int i = 1; i < m + 1; ++i) {
        dp[0][i] = dp[0][i - 1] + abs(b[i - 1]);
    }
    for (int i = 1; i < n + 1; ++i) {
        for (int j = 1; j < m + 1; ++j) {
            if (a[i - 1] == b[i - 1]) dp[i][j] = dp[i - 1][j - 1];
            else dp[i][j] = min(abs(a[i-1] - b[j-1]) + dp[i - 1][j - 1], min(dp[i - 1][j] + abs(a[i - 1]), dp[i][j - 1] + abs(b[j - 1])));
        }
    }
    cout << dp[n][m];
    return 0;
}
// vx公众号关注TechGuide 获取完整题解

import java.util.*;

// 未验证
public class BeiShuZijiChongxinzuo {
    /**
     * 使用回溯法，把所有每个数组的结果遍历存下来
     * 然后用map记录当前结果下，操作的次数
     * @param args
     */

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String A = scanner.next(), B = scanner.next();

        // 存储数字AB变化后的结果，以及变化后需要的步数
        Map<Integer, Integer> mapA = new HashMap<>();
        Map<Integer, Integer> mapB = new HashMap<>();

        dfs(mapA, A, 0, 0, 0);
        dfs(mapB, B, 0, 0, 0);

        int ans = Integer.MAX_VALUE;
        for (Integer a : mapA.keySet()) {
            for (Integer b : mapB.keySet()) {
                if (a % b == 0 || b % a == 0) {
                    ans = Math.min(ans, mapA.get(a) + mapB.get(b));
                }
            }
        }

        System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);
    }

    // 使用dfs得到所有的变化
    // 感觉对一个正数做加一个数字少一个数字的变化，用String好处理一点
    public static void dfs(Map<Integer, Integer> map, String str, int curIndex, int val, int opCount) {
        // 选完了
        if (curIndex == str.length()) {
            if (val != 0) {
                map.put(val, str.length() - opCount);
            }

            return;
        }

        // 不选，表示去掉，操作次数+1
        dfs(map, str, curIndex + 1, val, opCount + 1);

        // 选
        // 回溯，其实如果val写在里面，就不需要此处加上，后面减去了
        // 其实val在后面也没必要减去，因为这个是局部变量，也不是引用类型
        val = val * 10 + (str.charAt(curIndex) - '0');
        dfs(map, str, curIndex + 1, val, opCount);
        val = (val - (str.charAt(curIndex) - '0')) / 10;
    }
}

// 未验证
import java.util.*;
import java.util.stream.Collectors;

public class SanYuanZu {
    // 注意，要从1开始，0的话，+lowbit(0)上不去，死循环了
    static int N = 1;
    static int[] tr;
    static int lowbit(int x) {
        return x & (-x);
    }

    static void update(int x, int value) {
        for (int i = x; i < N; i += lowbit(i)) {
            tr[i] += value;
        }
    }

    static int query(int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(x)) {
            ans += tr[i];
        }
        return ans;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] nums = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();

        // 离散化，1 treeset排序去重
        Set<Integer> set = Arrays.stream(nums).boxed().collect(Collectors.toCollection(() -> new TreeSet<>((a, b) -> b - a)));
        // 2 map编号，这里没有用stream是因为，编号递增不能放入lambda表达式，因为他需要final的量
        Map<Integer, Integer> map = new HashMap<>();
        for (Integer num : set) {
            map.put(num, N++);
        }

        // 3 然后根据编号，反映给原始数组nums，此处完整的lambda表达式为 num -> { return map.get(num);}
        nums = Arrays.stream(nums).map(map::get).toArray();

        int[] l = new int[N+10], r = new int[N + 10];
        tr = new int[N + 10];
        // 右边的，需要先全部放进去
        for (int num : nums) {
            r[num] += 1;
        }

        int ans = 0;
        // 注意，这个num是离散化之后映射的结果了
        for (int num : nums) {
            // set是从大到小排序的
            // 遍历到该num的时候，这个数是先不算的，需要找到他的左右两边比他大的，相等的
            // query的时候，由于是严格大于，所以需要-1。
            ans += query(num-1);

            // 之前的去掉
            update(num, -l[num] * r[num]);
            l[num] += 1;
            r[num] -= 1;
            // 放入新的
            update(num, l[num] * r[num]);
        }

        System.out.println(ans);
    }
}

/**
给一个数字，这个数字十进制下每个数位的异或和，就是美丽数。
然后询问T次，每次给定区间L，R，t求区间中美丽数字为t的个数。
那么这个个数题目，是定向的等于t，所以其实桶的思想差不多了（而且t的范围不大，最多16），而不会计算前缀的个数吧？？
可以用一点类似莫队的思想，将LR区间排序，每次算一点
**/

import java.util.*;

public class ConferenceTime {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int T = Integer.parseInt(scanner.nextLine());

        while (T-- != 0) {
            int n = Integer.parseInt(scanner.nextLine());

            int[][] times = new int[n][2];
            for (int i = 0; i < n; i++) {
                times[i] = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();
            }

            // 先将会议时间按照start排序
            Arrays.sort(times, (time1, time2) -> time1[0] - time2[0]);

            // 表示从0～i时间的最长会议时间，这是个子问题
            int[] dp = new int[24];

            for (int i = 0; i < 1; i++) {
                int start = times[i][0], end = times[i][1];

                // 还是一维的想起来简单点
                // 对于这个会议，我看看end之后的每个时间，是取还是不取，更新
                // 需要根据start排序的，因为这样的话，我在这个会议使用那个dp[start]的时候，这个dp[start]是肯定不会再更新了
                // 因为按照start排序了，而且是更新每次end（包括）之后的，即使是更新start（不包括）之后，也不会变更了。
                for (int j = end; j < 24; j++) {
                    dp[j] = Math.max(dp[start] + end - start, dp[j]);
                }
            }

            Arrays.stream(dp).forEach(num -> System.out.print(num + " "));
            System.out.println(dp[23]);
        }
    }
}

/*
案例：
1
6
15 17
8 11
10 16
11 12
13 15
9 12
 */


import java.util.*;

public class ConferenceTime {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int T = Integer.parseInt(scanner.nextLine());

        while (T-- != 0) {
            int n = Integer.parseInt(scanner.nextLine());

            int[][] times = new int[n][2];
            for (int i = 0; i < n; i++) {
                times[i] = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();
            }

            // 先将会议时间按照start排序
            Arrays.sort(times, (time1, time2) -> time1[0] - time2[0]);

            // 第一维用 + 1，就不用考虑边界问题了
            // 第一维表示会议编号，0表示不取，第二维表示从0～i时间的最长会议时间，这是个子问题
            int[][] dp = new int[times.length + 1][24];

            // 边界，不用，不取的时候是0，dp0表示不取货物

            for (int i = 1; i <= times.length; i++) {
                int start = times[i-1][0], end = times[i-1][1];

                // 这个就是理解一下，
                // 如果j小于end，那么这个会议是加不进去的，所以直接等于前面的
                // 如果j大于，那么考虑加上这个和不加上这个，那一个更大取哪一个
                // 此处的会议是需要根据start排序的，因为不排序的话，需要用的那个dp[i-1][start]这次更新了，下次还会被更新到，但是前面已经用过了，导致出错
                for (int j = 0; j < 24; j++) {
                    if (j < end) {
                        dp[i][j] = dp[i-1][j];
                    } else {
                        dp[i][j] = Math.max(dp[i-1][start] + end - start, dp[i-1][j]);
                    }
                }
            }

            Arrays.stream(dp[times.length]).forEach(num -> System.out.print(num + " "));
            System.out.println(dp[times.length][23]);
        }
    }
}

public class CangKu {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int M = Integer.parseInt(scanner.nextLine());
        // 输入 + 从大到小排序
        int[] nums = Arrays.stream(scanner.nextLine().split(" "))
                .mapToInt(Integer::valueOf)
                .toArray();

        // 考虑动态规划，看一般的背包能装多少
        int n = nums.length;
        // 表示背包的一半的重量
        int m = Arrays.stream(nums).sum() / 2;
        // 对一半重量进行01背包问题dp
        int[] dp = new int[m + 1];


        for (int i = 1; i < n + 1; i++) {
          	// 因为一维dp，所以反着来
            for (int j = m; j >= 0; j--) {
                if (j < nums[i - 1]) {
                    // 装不下
                    dp[j] = dp[j];
                } else {
                    dp[j] = Math.max(dp[j], dp[j - nums[i-1]] + nums[i - 1]);
                }
            }
        }

        System.out.println(Arrays.stream(nums).sum() - dp[m]);
    }
}

class Solution {
    public int maxPoints(int[][] ps) {
        int n = ps.length;
        int ans = 1;
        for (int i = 0; i < n; i++) {
            Map<String, Integer> map = new HashMap<>();
            // 由当前点 i 发出的直线所经过的最多点数量
            int max = 0;
            for (int j = i + 1; j < n; j++) {
                int x1 = ps[i][0], y1 = ps[i][1], x2 = ps[j][0], y2 = ps[j][1];
                int a = x1 - x2, b = y1 - y2;
                int k = gcd(a, b);
                String key = (a / k) + "_" + (b / k);
                map.put(key, map.getOrDefault(key, 0) + 1);
                max = Math.max(max, map.get(key));
            }
            ans = Math.max(ans, max + 1);
        }
        return ans;
    }
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

public static class ShowMeBug1 {
    // 本题面试官已设置测试用例
    // 请根据题目要求确定返回值类型和参数列表(输入)
    public int lastGarbageSize(int[] garbages) {
        // 在这⾥写代码
        // 使用动态规划
        int n = garbages.length;
        int sum = 0;
        for (int g: garbages) {
            sum += g;
        }
        int m = sum / 2;
        boolean[][] dp = new boolean[n + 1][m + 1];

        // 边界，0表示不取物品的时候
        dp[0][0] = true;

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

                if (j < garbages[i-1]) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = dp[i-1][j] || dp[i-1][j - garbages[i-1]];
                }
            }
        }

        for (int j = m; j>=0; j--) {
            if (dp[n][j]) {
                return sum - 2 * j;
            }
        }

        return 0;
    }
}

public static class ShowMeBug {
    // 本题面试官已设置测试用例
    // 请根据题目要求确定返回值类型和参数列表(输入)
    public int[][] mergeCard(int[][] cards) {
        // 在这⾥写代码

        List<int[]> ans = new ArrayList<>();
        int count = 0;

        // 按照start从小到大排序
        Arrays.sort(cards, (card1, card2) -> card1[0] - card2[0]);

        // 放入第一个
        ans.add(cards[0]);

        for (int i = 1; i < cards.length; i++) {
            int b = cards[i][0], e = cards[i][1];

            // 如果没有相交
            if (b > ans.get(count)[1]) {
                ans.add(cards[i]);
                count += 1;
            } else {
                // 相交
                ans.get(count)[1] = Math.max(e, ans.get(count)[1]);
            }
        }

        // 将List转为int
        int[][] newAns = new int[ans.size()][2];
        for (int i = 0; i < ans.size(); i++) {
            newAns[i][0] = ans.get(i)[0];
            newAns[i][1] = ans.get(i)[1];
        }

        return newAns;
    }
}

import java.util.*;

public class Main3 {
    public static class TreeNode {
        List<TreeNode> childs;
        int val;

        TreeNode(int val) {
            this.val = val;
            childs = new ArrayList<>();
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = Integer.parseInt(scanner.nextLine());
        visited = new boolean[n + 1];

        TreeNode[] nodes = new TreeNode[n + 1];
        for (int i = 0; i < n + 1; i++) {
            nodes[i] = new TreeNode(i);
        }

        for (int i = 0; i < n-1; i++) {
            int temp = scanner.nextInt();
            // 注意这里i+2，因为从0开始
            nodes[temp].childs.add(nodes[i+2]);
        }

        TreeNode root = nodes[1];

        dfs(root);

        System.out.println(ans);
    }

    static int n = 0;
    static int ans = 0;
    static boolean[] visited;
    public static void dfs(TreeNode node) {
        // 如果该节点有子节点，并且没被访问过，那么可能能将该节点与子节点配对
        if (!node.childs.isEmpty() && !visited[node.val]) {
            // 先将子节点递归
            for (int i = 0; i < node.childs.size(); i++) {
                if (!node.childs.get(i).childs.isEmpty()) {
                    dfs(node.childs.get(i));
                }
            }

            // 子节点递归完了，才轮到自己，与某个没有被配对的子节点配对即可，若没有就没有喽
            for (int i = 0; i < node.childs.size(); i++) {
                if (!visited[node.childs.get(i).val]) {
                    visited[node.childs.get(i).val] = true;
                    visited[node.val] = true;

                    ans += 1;

                    return;
                }
            }
        }
    }
}

import java.util.*;

public class Main2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), m = scanner.nextInt();
        scanner.nextLine();
        int[] indexs = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();
        int[] nums = IntStream.range(0, n).map(i -> i+1).toArray();

        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            queue.offerLast(i + 1);
        }

        for (int i = 0; i < m; i++) {
            queue.offerFirst(indexs[i]);
        }

        Set<Integer> set = new HashSet<>();

        int size = queue.size();
        for (int i = 0; i < size; i++) {
            int temp = queue.pollFirst();
            if (!set.contains(temp)) {
                System.out.print(temp + " ");
                set.add(temp);
            }
        }
    }
}

import java.util.*;

public class Main3 {
    /**
     * 一共要割m-1刀
     * @param args
     */
    static int n, m;
    static String s;
    static int[] kehu;
    static String[] kehuStrs;
    static int ans;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        scanner.nextLine();
        s = scanner.nextLine();

        kehu = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();
        kehuStrs = new String[m];
        for (int i = 0; i < m; i++) {
            kehuStrs[i] = scanner.nextLine();
        }

        dfsTrace(0, 0, new ArrayList<>());

        System.out.println(ans);
    }

    /**
     * 回溯 + dfs，curIndex表示该间隙割还是不割
     */
    public static void dfsTrace(int preIndex, int curIndex, List<String> strs) {
        if (strs.size() == m - 1 && curIndex <= n - 1) {
            strs.add(s.substring(preIndex));

            boolean[] visited = new boolean[m];
            out: for (int j = 0; j < m; j++) {
                for (int i = 0; i < m; i++) {
                    if (!visited[i] && strs.get(j).equals(kehuStrs[i])) {
                        visited[i] = true;
                        continue out;
                    }
                }

                strs.remove(strs.size() - 1);
                return;
            }

            strs.remove(strs.size() - 1);
            ans += 1;
            return;
        }

        if (curIndex >= n - 1) {
            return;
        }

        // 不割
        dfsTrace(preIndex, curIndex + 1, strs);

        // 割
        strs.add(s.substring(preIndex, curIndex + 1));
        dfsTrace(curIndex + 1, curIndex + 1, strs);
        strs.remove(strs.size() - 1);
    }
}

import java.util.*;

// 未验证
public class Main4 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), b = scanner.nextInt();
        scanner.nextLine();

        int[] p = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();
        int[] t = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();

        if (p[0] > b) {
            System.out.println(-1);
            return;
        }

        // 注意，题目有两个限制，一个是电量限制，一个是要时间最小
        // 所以可以在每一次时间，（看作背包），看看该最小电量能否满足，然后取最小时间
        // 也就是说，在某个时间限制下，我先求能用到的最小电量，然后看能否满足。此处没有价值问题，感觉根背包稍微一点不一样？
        // 但是这种朴素做法会超时，所以考虑把时间二分来做
        // 注意，此处的机器人只能往右，而且是并行执行的，所以考虑从右往做算dp



        int left = 1, right = Arrays.stream(t).sum();
        int ans = 0;

        while (left <= right) {
            int mid = left + (right - left >> 1);

            // 找到满足的最小的
            if (check(mid, n, p, t, b)) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        // 最终状态right < left，left满足，right不满足
        System.out.println(ans);
    }

    public static boolean check(int time, int n, int[] p, int[] t, int b) {
        // 表示在某个固定时间下，收i～n件衣服的最少电量
        // 所以dp[1]才是收所有衣服的最少电量
        int[] dp = new int[n+2];

        // 边界，注意t和p是从0开始的，而dp是从1开始的，不要搞混了
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[n+1] = 0;

        // 以第i个，收到第j个，j是大于i的，由于从后往前，dp[j]已有最小电量，现在算dp[i]
        // 就是说，dp[i]的最少电量，可以由机器人i往后一段时间到每个j来遍历的得到最小电量
        for (int i = n; i >= 1; i--) {
            // 注意此处j要从n+1，因为j不包括的，所以机器人i收到n，是要j在n+1
            for (int j = n+1; j > i; j--) {
                // 此处j是不包括的，因为dp[j]里面有j了
                if ((j - i) * t[i-1] <= time) {
                    dp[i] = Math.min(dp[i], dp[j] + p[i-1]);
                }
            }
        }

        return dp[1] <= b;
    }
}