P8873 [Chuanzhi Cup #5 Preliminary] E - Mellie’s Market Economics.

Mellie took an economics elective this semester. However, since her major is psychology, she is really not good at analyzing economics. Because of this, she often complains that she cannot learn it and wants to drop the course. But if she drops it now, she will not have enough credits this semester. So, based on what she “experienced in a dream,” she “made up” a market model that is simple to the point of being unrealistic, and wrote an essay using this model. To make it easier to create charts, she needs to write a program to query the market trade balance at each moment.

The daily trade balance in the market can be seen as a periodic sequence $a$: $\color{red}[0],\color{blue}[0,\allowbreak 1,\allowbreak 0,\allowbreak -1,\allowbreak 0],\color{red}[0,\allowbreak 1,\allowbreak 2,\allowbreak 1,\allowbreak 0,\allowbreak -1,\allowbreak -2,\allowbreak -1,\allowbreak 0],\allowbreak \color{blue}[0,\allowbreak 1,\allowbreak 2,\allowbreak 3,\allowbreak 2,\allowbreak 1,\allowbreak 0,\allowbreak -1,\allowbreak -2,\allowbreak -3,\allowbreak -2,\allowbreak -1,\allowbreak 0]\dots$. More specifically, $a$ can be divided into infinitely many segments. The content of the $i$-th segment is $\{0,\allowbreak 1,\allowbreak \cdots,\allowbreak i,\allowbreak i-1,\allowbreak \cdots,0,\allowbreak -1,\allowbreak \cdots,\allowbreak -i,\allowbreak -i+1,\allowbreak \cdots 0\}$. The figure below shows the plot of some of the first points in sequence $a$ on the coordinate axes:  Now Mellie makes $q$ queries to the market. Each time, she is given an integer $k$ and wants to find the value of $a_k$.

- The first line contains a positive integer $q$, which represents the number of queries. - The next $q$ lines each contain a positive integer $k$, describing each query.

- Output a total of $q$ lines. For each query, output the corresponding result.

Constraints: for all testdata, $1 \leq q \leq 10^5$, $1 \leq k \leq 4\times 10^{18}$. Translated by ChatGPT 5