题目描述

在像素小镇里，有一位名叫伞伞的小画家。他有一块巨大的魔法画布，大小是 $10^9×10^9$ 个像素点，左上角是 $(1,1)$，右下角是 $(10^9,10^9)$。最近，伞伞迷上了画字母 Z，他觉得这个字母既帅气又神秘。

画一个边长为 $d$（$d>2$）的 Z 字，需要按照一个固定的顺序描点：

1. 先画最上面的一横，从左到右；
2. 然后画中间的对角线，从右上角往左下角斜着画；
3. 最后画最下面的一横，从左到右。

例如，当 $d=3$ 时，画出的图案是（字符 . 表示画布上的空白处，字符 * 表示伞伞画的地方）：

***
.*.
***

画点的顺序是：$(1,1),(1,2),(1,3),(2,2),(3,1),(3,2),(3,3)$。

当 $d=4$ 时，图案是：

****
..*.
.*..
****

顺序是：$(1,1),(1,2),(1,3),(1,4),(2,3),(3,2),(4,1),(4,2),(4,3),(4,4)$。

聪明的你一眼就看出伞伞一共需要画 $3d - 2$ 个字符。现在，伞伞想挑战你：他选定了左上角的位置 $(x,y)$ 和边长 $d$，然后按顺序开始画。请你帮他算出，他画的第 $k$ 个字符会落在哪个坐标上？注意，画布足够大，不会超出边界。

输入格式

第一行一个正整数 $T$，表示数据组数。

对于每组测试数据，输入一行三个正整数 $x,y,d,k$，含义如上所述。

输出格式

对于每组数据，输出两个整数，表示伞伞画的第 $k$ 个字符的坐标。

5
10 10 4 4
10 10 4 5
10 10 4 6
10 10 4 7
10 10 4 10

10 13
11 12
12 11
13 10
13 13

数据规模与约定

下发文件

下发文件对应子任务 $3$。

对于 $100\%$ 的数据：保证 $1 \leq T \leq 10,1 \leq x,y \leq 10^9,3 \leq d \leq 10^9,1 \leq k \leq min(10^9,3d-2)$ ，保证画布能够画的下边长为 $d$ 的字母 z 的像素矩阵。