Bước Nhảy Theo Chẵn Lẻ

Một điểm bắt đầu tại tọa độ nguyên $x_0$ trên trục số. Ở bước thứ $i$, nó dịch đúng $i$ đơn vị:

• nếu tọa độ ngay trước bước là số chẵn, nó đi sang trái;
• nếu tọa độ ngay trước bước là số lẻ, nó đi sang phải.

Quy ước chẵn/lẻ áp dụng như thường lệ cho cả số âm. Với mỗi bộ test, hãy tính tọa độ sau đúng $n$ bước.

Input

• Dòng đầu chứa số nguyên $t$ - số bộ test.
• Mỗi bộ test chứa hai số nguyên $x_0$ và $n$: tọa độ ban đầu và số bước.

Output

• Với mỗi bộ test, in tọa độ sau đúng $n$ bước.

Constraints

• $1\le t\le 10^4$.
• $-10^{14}\le x_0\le 10^{14}$.
• $0\le n\le 10^{14}$.
• Ở bước thứ $i(1\le i\le n)$, độ dài bước bằng $i$; hướng được quyết định từ parity của tọa độ ngay trước bước.

Scoring

• Subtask $1$ ($50\%$ số điểm): $t\le 100$ và $n\le 10^5$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

6
0 0
2 1
3 2
-5 3
10 4
-2 5

0
1
2
-9
10
-7