P16937 Book of Time.

:::info[Problem Background] Frieren stood in front of the "Sunken Star Library" and gently opened that thick and ancient "Book of Time". Between the pages there were no ordinary words, only layers of spell patterns that flowed slowly like star trails, as if time itself was quietly sleeping inside it. She raised her hand, and the magic at her fingertips sank little by little into the pages. Pale golden light spread out with it, covering Fern and Stark as well. In the next moment, everything around them began to blur. The wind stopped. The dust stopped. The collapsed ruins in the distance and the dim sky also slowly rippled and twisted like reflections thrown into water. Countless tiny points of light floated up from between the pages, circling up along their feet and the hems of their clothes, as if they were turning some already-off-course history back, inch by inch, to its original place. "Hold on to me," Frieren said softly. :::

The spell pattern of the "Book of Time" is a huge, constantly changing equilateral triangle. For convenience, we build a Cartesian coordinate system. The coordinates of the vertices of the equilateral triangle in the coordinate system are $(-1, 0)$, $(1, 0)$, and $(0, \sqrt{3})$. Initially, the spell ID of this triangle is $1$, and the time weight at each vertex is $1$. The spell pattern of the "Book of Time" needs to undergo $q$ operations to be activated normally. Each operation is one of the following: - `query i` means querying the sum of the time weights of the three vertices of the triangle whose spell ID is $i$. Frieren must feed exactly that amount of magic (equal to the sum of weights) to correctly activate the spell; - `update i y` means changing the time weights of all three vertices of the triangle whose spell ID is $i$ to $y$; - `extend i` means extending the triangle whose spell ID is $i$ into four child triangles. Specifically, we define: - $AB$ is the side of triangle $i$ that is parallel to the $x$ axis, and the $x$ coordinate of $A$ is less than the $x$ coordinate of $B$; - $C$ is the third vertex of triangle $i$. If the $y$ coordinate of $C$ is greater than the $y$ coordinates of $A$ and $B$, then triangle $i$ is an **upright triangle**; otherwise it is an **inverted triangle**; - Let the midpoint of $AB$ be $D$, the midpoint of $AC$ be $E$, and the midpoint of $BC$ be $F$. Then for an **upright triangle**, the four child triangles are $\triangle ADE, \triangle DBF, \triangle DEF, \triangle CEF$, and their spell IDs are $4i, 4i+1, 4i+2, 4i+3$ respectively. For an **inverted triangle**, the four child triangles are $\triangle DBF, \triangle ADE, \triangle DEF, \triangle CEF$, and their spell IDs are $4i, 4i+1, 4i+2, 4i+3$ respectively; - After extension, if a vertex of a child triangle already has a time weight, the weight remains unchanged; otherwise its weight is $1$; - It is guaranteed that the spell IDs of the child triangles after extension are less than $10^9$. The figure below shows the effect of the extend operation. Together with the sample input, you can understand the detailed process of the extend operation more intuitively. For each `query i` operation, Frieren needs to know the sum of the time weights of the three vertices of the triangle whose spell ID is $i$. 

The first line contains an integer $q(1\leq q\leq 10^5)$, representing the number of spell transformations of the "Book of Time". In the following $q$ lines, each line represents one operation: - `query i` means querying the sum of the time weights of the three vertices of the triangle whose spell ID is $i$; - `update i y` means changing the time weights of all three vertices of the triangle whose spell ID is $i$ to $y(1\leq y\leq 10^9)$; - `extend i` means extending the triangle whose spell ID is $i$ into four child triangles, as defined above. The input guarantees that the spell ID in every operation is a valid and existing triangle spell ID.

Output several lines, each containing one integer, representing the result of each `query` operation.

:::info[Problem Background] --- As the last spell pattern fully closed, the light on the "Book of Time" finally stopped spreading outward. Instead, like a tide returning home, it quietly flowed back, slowly, toward deeper places. In that instant, the deviated timelines were corrected again, and the world seemed to quietly let out a long sigh in a place no one noticed. Right after that, everything in the "Sunken Star Library" began to restore itself against memory. Deep in the front courtyard, those originally silent black "Celestial Balance Armillary" were unsealed again. A steady and dim light slowly lit up along the spell patterns at the base. The guardian monsters that had once been knocked down also awakened again in the echo of ancient magic, and quietly returned to the position they were meant to watch over. The hall torn apart by the great battle recovered little by little. The collapsed stone pillars stood up again, the cracked ground mended again, and the scattered pages and dust quietly fell back to their original places. Only those traces of weathering and cracks that could not be completely erased still remained between the stone walls and the steps, as if the thousand years had never truly left here. Farther away, the once-decrypted "Astral Stele Needle" also returned to its alternating bright and dark flicker, as if the stars were calling and responding in the distant night sky. And those damaged "Arch-Chen Sealing Device" also reassembled and restored in silence, once again guarding the "Sunken Star Library" in the center of the forest, not allowing anyone to easily reach its true core. When the last bit of light sank into the depths of time, Frieren and her companions were already standing again in that familiar forest. The wind passed through the tall treetops, bringing a damp and fresh scent of grass and leaves. The morning mist still slowly lingered among the woods, as if nothing had happened. Fern froze for a moment, lowered her head to look at her backpack. The mana-gathering stone inside was still lying there quietly. The magic sealed within was complete and warm, not consumed even by the slightest bit. It was as if that long and difficult journey earlier, those hard fights, those mechanisms, those mysteries that once touched a thousand years ago, were only a short illusion reflected through the cracks of time. But they all knew it was not a dream. Because in Frieren's arms, there was no longer the "Book of Time". That ancient tome carrying countless possibilities finally returned to where it was meant to stay. It was no longer a book that anyone could take away. Instead, it turned back into that thick and silent ancient magic, quietly floating at the center of the throne in the deepest part of the "Sunken Star Library", waiting for the next adventurer who could reach this place, to talk with the grand librarian from a thousand years ago. Perhaps, to that ancient person who had watched for far too long, what truly mattered was never just one particular spell, or one precious tome. Rather, it was giving later generations a chance to witness a thousand years of changes in history, to glimpse how different lives gather and part in time, and to understand why magic, civilization, and memory are passed down. Perhaps this is the true meaning of the "Sunken Star Library". The woods fell quiet for a moment. Then Stark let out a long breath. Fern also smiled softly, as if she had finally put some heavy yet correct choice back into her heart. Frieren raised her head to look at the daylight falling through the gaps between the branches. The wind gently lifted the tips of her silver-white hair. Her expression was still calm, but it also carried a very faint softness compared to usual. "If it were the hero Himmel... maybe he would make the same choice." ::: Translated by ChatGPT 5