1281. A Grid Coordinate as a Single Key

A grid position is a row r and a column c, each from 0 to 100000. It must become a single integer key, with the column in the LOW 17 bits:

key = (r << 17) | c

Answer q instructions. P r c prints the key; U key prints r and c.

P 1 1 -> 131073 U 131073 -> 1 1 P 100000 100000 -> 13107300000

## What most people try first

A 16-bit column field, because 100000 looks like it should fit in "about sixteen bits". It does not: 2^16 = 65536 and the column reaches 100000, so a 16-bit field wraps and two different positions collide. The smallest width that works is 17, because 2^17 = 131072 is the first power of two above 100000. Getting that wrong does not crash; it silently maps (0, 100000) and (1, 34464) to the same key, and whatever structure is keyed by it starts losing entries.

So the first step of any packing is to compute the width from the BOUND, not from a guess, which is what #1285 is about.

## The arithmetic

pack: key = (r << 17) | c unpack: r = key >> 17 c = key & 131071

The mask is (1 << 17) - 1 = 131071. The row needs no mask on unpacking, because it occupies everything above bit 16 and nothing was packed above it.

## Why pack at all

A key like this is how a grid is used as a hash-map key, or how a (row, column) pair is stored in a single long column, or how a visited set becomes one flat array instead of a two-dimensional one. The equivalent arithmetic form r * 131072 + c is exactly the same number, because shifting left by 17 IS multiplying by 2^17, and it is the form to use in a language where the shift does not reach far enough.

## Width

The row reaches 100000, which needs 17 bits, so the key occupies 34 bits and reaches 100000 * 131072 + 100000 = 13107300000. That is past the 2147483647 a signed 32-bit integer holds by a factor of six, so the key needs a 64-bit type: long long in C and C++, long in Java.

JavaScript cannot use << here at all, and this was run rather than assumed. 100000 << 17 evaluates to 222298112 instead of 13107200000, because << coerces to signed 32 bits and throws away everything above bit 31. The full expression (100000 << 17) | 100000 gives 222398112 where the answer is 13107300000. The reference solution therefore uses the arithmetic form, r * 131072 + c, which is exact because 13107300000 is well below 2^53 = 9007199254740992; unpacking uses Math.floor(key / 131072) and key % 131072. BigInt would also work and is slower. Splitting the value like this is the standard answer whenever JavaScript needs more than 31 value bits.

Constraints - `1 ≤ q ≤ 100000` - `0 ≤ r ≤ 100000` and `0 ≤ c ≤ 100000` - every `key` given to `U` is the packing of some valid `(r, c)` pair