題目描述

一天一隻草蜢在實數軸上玩「左右橫跳」這個遊戲。它會在點 x 出發，並在進行 n 次的跳躍。

它第k次的跳躍規則如下：(m 為第 k 次跳躍前的點)

• 若它在一偶數點上，它就會向負方向(向左)跳 k 個單位，到點 m-k 上
• 若它在一奇數點上，它就會向正方向(向右)跳 k 個單位，到點 m+k 上

請求出，草蜢連續進行 n 次跳躍後，身處點的座標。 

(温馨提示: 系統能根據完成程度給序部分分數，但若要完全解決這題需要能處理 n 較大的情況)

輸入格式

第一行有一正整數 T (1 <= T <= 100)，表示接下來有 T 組獨立的測資。

每個測資中共一行，給定兩個整數代表一對 x n，

-10¹² <= x <= 10¹², 0 <= n <= 10¹⁰。

輸出格式

共輸出 T 行，分別為 T 個測資的答案。對第 i 個測資請輸出草蜢最後身處的位置。

Samples

["4\r\n3 1\r\n2 2\r\n10 0\r\n-3 3","4\r\n-2 5\r\n0 2\r\n6 6\r\n99999991 2"]

["4\r\n3\r\n10\r\n-7","-7\r\n1\r\n7\r\n99999990"]

提示

範例輸入#1中，第一個測資開始點是 3，是一個奇數點，所以經1次後會向右 (正方向) 跳到 3+1=4；第二個測資起始是 2，跳 1 次後(向左)會到 2-1=1，而由於1是奇數點再跳1次 (向右) 會到 1+2=3；第三個測資由10 開始且在 10 完結；第四個測資在 -3 開始，隨後依次跳到 -2, -4, -7。

備註

Codeforces Round #753 (Div. 3) P2

原始資料

• Zero1 題號：a451
• Hydro 題號：Z0451
• Locale：en_US
• Display：open