题目描述

今天是 10 月 24 日。 牛牛本来准备下班，产品经理却在工作群里发了一串消息： 增加一个需求。 刚才的需求撤回。 刚才那条撤回也撤回。 群机器人表示：我支持双重否定，你们继续。 工作群里共有 条历史消息，按发送时间从早到晚编号为 $1,2,\ldots,n$。每条消息属于以下两种类型之一： 新增需求 $1$ $w$： 如果这条消息最终有效，就给牛牛增加 w 个单位的加班量。 批量撤回 $2$ $l$ $r$： 如果这条消息最终有效，就对编号在 $[l,r]$ 内的每条历史消息进行一次撤回。保证 $1\le l\le r$ 机器人的撤回规则如下： 新增需求和批量撤回消息都可以被撤回，消息编号始终不变。 对同一条消息撤回偶数次，这条消息有效；撤回奇数次，这条消息无效。撤回零次也算偶数次。 只有最终有效的撤回消息，才会产生撤回效果。 一条撤回消息如果最终无效，就不对它的目标产生任何影响。 严格地说，对于任意一条历史消息 $i$，统计其后所有最终有效、且目标包含 $i$ 的撤回消息的数量：数量为偶数则 $i$ 有效，为奇数则 $i$ 无效。由于撤回只能指向更早的消息，所有消息的最终状态可以唯一确定。 牛牛获得了一个程序员节福利：他可以在所有历史消息之后，追加至多一条单独的撤回消息，指定撤回第 $k$ 条历史消息，其中 $1\le k\le n$。这条新消息本身一定有效，也要参与上述规则的计算。牛牛也可以什么都不发，此时记 $k=0$。 指定的历史消息可以属于任意类型，也可以是一条原本已经无效的消息。追加消息后，必须根据全部消息重新确定最终状态。 最终加班量，是所有最终有效的新增需求消息的 $w$ 之和。 请你帮牛牛选择 $k$，使最终加班量最小。如果有多个选择达到最小加班量，输出其中最小的 $k$。 今天不是程序员节吗？为什么程序员不放假？？？官方中文

输入格式

第一行输入一个整数 $T$，表示测试用例组数，满足 $1\le T\le 100$。官方中文

对于每组测试用例：官方中文

第一行输入一个整数 $n$，满足 $1\le n\le 1024$。 接下来 $n$ 行，按时间顺序描述历史消息。 若为新增需求，输入 $1$ $w$，满足 $1\le w\le 10^9$。 若为批量撤回，输入 $2$ $l$ $r$，满足 $1\le l\le r<i$，其中 $i$ 是当前消息编号。官方中文

保证同一个测试文件中所有测试用例的 $n$ 之和不超过 $4096$。官方中文

输出格式

对于每组测试用例，输出一行两个整数 $W$ 和 $k$，分别表示能够达到的最小最终加班量，以及达到该加班量的最小选择编号。官方中文

$k=0$ 表示不追加任何消息。请使用能够容纳答案的整数类型。官方中文