2 * common functions for Indeo Video Interactive codecs (Indeo4 and Indeo5)
4 * Copyright (c) 2009 Maxim Poliakovski
6 * This file is part of FFmpeg.
8 * FFmpeg is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
13 * FFmpeg is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with FFmpeg; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
25 * This file contains functions and data shared by both Indeo4 and
29 #define BITSTREAM_READER_LE
32 #include "ivi_common.h"
33 #include "libavutil/common.h"
36 extern const IVIHuffDesc ff_ivi_mb_huff_desc[8]; ///< static macroblock huffman tables
37 extern const IVIHuffDesc ff_ivi_blk_huff_desc[8]; ///< static block huffman tables
39 VLC ff_ivi_mb_vlc_tabs [8];
40 VLC ff_ivi_blk_vlc_tabs[8];
43 * Reverse "nbits" bits of the value "val" and return the result
44 * in the least significant bits.
46 static uint16_t inv_bits(uint16_t val, int nbits)
51 res = av_reverse[val] >> (8-nbits);
53 res = ((av_reverse[val & 0xFF] << 8) + (av_reverse[val >> 8])) >> (16-nbits);
58 int ff_ivi_create_huff_from_desc(const IVIHuffDesc *cb, VLC *vlc, int flag)
60 int pos, i, j, codes_per_row, prefix, not_last_row;
61 uint16_t codewords[256]; /* FIXME: move this temporal storage out? */
64 pos = 0; /* current position = 0 */
66 for (i = 0; i < cb->num_rows; i++) {
67 codes_per_row = 1 << cb->xbits[i];
68 not_last_row = (i != cb->num_rows - 1);
69 prefix = ((1 << i) - 1) << (cb->xbits[i] + not_last_row);
71 for (j = 0; j < codes_per_row; j++) {
72 if (pos >= 256) /* Some Indeo5 codebooks can have more than 256 */
73 break; /* elements, but only 256 codes are allowed! */
75 bits[pos] = i + cb->xbits[i] + not_last_row;
76 if (bits[pos] > IVI_VLC_BITS)
77 return -1; /* invalid descriptor */
79 codewords[pos] = inv_bits((prefix | j), bits[pos]);
87 /* number of codewords = pos */
88 return init_vlc(vlc, IVI_VLC_BITS, pos, bits, 1, 1, codewords, 2, 2,
89 (flag ? INIT_VLC_USE_NEW_STATIC : 0) | INIT_VLC_LE);
92 void ff_ivi_init_static_vlc(void)
95 static VLC_TYPE table_data[8192 * 16][2];
96 static int initialized_vlcs = 0;
100 for (i = 0; i < 8; i++) {
101 ff_ivi_mb_vlc_tabs[i].table = table_data + i * 2 * 8192;
102 ff_ivi_mb_vlc_tabs[i].table_allocated = 8192;
103 ff_ivi_create_huff_from_desc(&ff_ivi_mb_huff_desc[i], &ff_ivi_mb_vlc_tabs[i], 1);
104 ff_ivi_blk_vlc_tabs[i].table = table_data + (i * 2 + 1) * 8192;
105 ff_ivi_blk_vlc_tabs[i].table_allocated = 8192;
106 ff_ivi_create_huff_from_desc(&ff_ivi_blk_huff_desc[i], &ff_ivi_blk_vlc_tabs[i], 1);
108 initialized_vlcs = 1;
111 int ff_ivi_dec_huff_desc(GetBitContext *gb, int desc_coded, int which_tab,
112 IVIHuffTab *huff_tab, AVCodecContext *avctx)
115 IVIHuffDesc new_huff;
118 /* select default table */
119 huff_tab->tab = (which_tab) ? &ff_ivi_blk_vlc_tabs[7]
120 : &ff_ivi_mb_vlc_tabs [7];
122 huff_tab->tab_sel = get_bits(gb, 3);
123 if (huff_tab->tab_sel == 7) {
124 /* custom huffman table (explicitly encoded) */
125 new_huff.num_rows = get_bits(gb, 4);
127 for (i = 0; i < new_huff.num_rows; i++)
128 new_huff.xbits[i] = get_bits(gb, 4);
130 /* Have we got the same custom table? Rebuild if not. */
131 if (ff_ivi_huff_desc_cmp(&new_huff, &huff_tab->cust_desc)) {
132 ff_ivi_huff_desc_copy(&huff_tab->cust_desc, &new_huff);
134 if (huff_tab->cust_tab.table)
135 free_vlc(&huff_tab->cust_tab);
136 result = ff_ivi_create_huff_from_desc(&huff_tab->cust_desc,
137 &huff_tab->cust_tab, 0);
139 av_log(avctx, AV_LOG_ERROR,
140 "Error while initializing custom vlc table!\n");
144 huff_tab->tab = &huff_tab->cust_tab;
146 /* select one of predefined tables */
147 huff_tab->tab = (which_tab) ? &ff_ivi_blk_vlc_tabs[huff_tab->tab_sel]
148 : &ff_ivi_mb_vlc_tabs [huff_tab->tab_sel];
155 int ff_ivi_huff_desc_cmp(const IVIHuffDesc *desc1, const IVIHuffDesc *desc2)
157 return desc1->num_rows != desc2->num_rows
158 || memcmp(desc1->xbits, desc2->xbits, desc1->num_rows);
161 void ff_ivi_huff_desc_copy(IVIHuffDesc *dst, const IVIHuffDesc *src)
163 dst->num_rows = src->num_rows;
164 memcpy(dst->xbits, src->xbits, src->num_rows);
167 int av_cold ff_ivi_init_planes(IVIPlaneDesc *planes, const IVIPicConfig *cfg)
170 uint32_t b_width, b_height, align_fac, width_aligned, height_aligned, buf_size;
173 ff_ivi_free_buffers(planes);
175 /* fill in the descriptor of the luminance plane */
176 planes[0].width = cfg->pic_width;
177 planes[0].height = cfg->pic_height;
178 planes[0].num_bands = cfg->luma_bands;
180 /* fill in the descriptors of the chrominance planes */
181 planes[1].width = planes[2].width = (cfg->pic_width + 3) >> 2;
182 planes[1].height = planes[2].height = (cfg->pic_height + 3) >> 2;
183 planes[1].num_bands = planes[2].num_bands = cfg->chroma_bands;
185 for (p = 0; p < 3; p++) {
186 planes[p].bands = av_mallocz(planes[p].num_bands * sizeof(IVIBandDesc));
187 if (!planes[p].bands)
188 return AVERROR(ENOMEM);
190 /* select band dimensions: if there is only one band then it
191 * has the full size, if there are several bands each of them
192 * has only half size */
193 b_width = planes[p].num_bands == 1 ? planes[p].width : (planes[p].width + 1) >> 1;
194 b_height = planes[p].num_bands == 1 ? planes[p].height : (planes[p].height + 1) >> 1;
196 /* luma band buffers will be aligned on 16x16 (max macroblock size) */
197 /* chroma band buffers will be aligned on 8x8 (max macroblock size) */
198 align_fac = p ? 8 : 16;
199 width_aligned = FFALIGN(b_width , align_fac);
200 height_aligned = FFALIGN(b_height, align_fac);
201 buf_size = width_aligned * height_aligned * sizeof(int16_t);
203 for (b = 0; b < planes[p].num_bands; b++) {
204 band = &planes[p].bands[b]; /* select appropriate plane/band */
207 band->width = b_width;
208 band->height = b_height;
209 band->pitch = width_aligned;
210 band->bufs[0] = av_malloc(buf_size);
211 band->bufs[1] = av_malloc(buf_size);
212 if (!band->bufs[0] || !band->bufs[1])
213 return AVERROR(ENOMEM);
215 /* allocate the 3rd band buffer for scalability mode */
216 if (cfg->luma_bands > 1) {
217 band->bufs[2] = av_malloc(buf_size);
219 return AVERROR(ENOMEM);
222 planes[p].bands[0].blk_vlc.cust_desc.num_rows = 0; /* reset custom vlc */
229 void av_cold ff_ivi_free_buffers(IVIPlaneDesc *planes)
233 for (p = 0; p < 3; p++) {
234 for (b = 0; b < planes[p].num_bands; b++) {
235 av_freep(&planes[p].bands[b].bufs[0]);
236 av_freep(&planes[p].bands[b].bufs[1]);
237 av_freep(&planes[p].bands[b].bufs[2]);
239 if (planes[p].bands[b].blk_vlc.cust_tab.table)
240 free_vlc(&planes[p].bands[b].blk_vlc.cust_tab);
241 for (t = 0; t < planes[p].bands[b].num_tiles; t++)
242 av_freep(&planes[p].bands[b].tiles[t].mbs);
243 av_freep(&planes[p].bands[b].tiles);
245 av_freep(&planes[p].bands);
249 int av_cold ff_ivi_init_tiles(IVIPlaneDesc *planes, int tile_width, int tile_height)
251 int p, b, x, y, x_tiles, y_tiles, t_width, t_height;
253 IVITile *tile, *ref_tile;
255 for (p = 0; p < 3; p++) {
256 t_width = !p ? tile_width : (tile_width + 3) >> 2;
257 t_height = !p ? tile_height : (tile_height + 3) >> 2;
259 if (!p && planes[0].num_bands == 4) {
263 if(t_width<=0 || t_height<=0)
264 return AVERROR(EINVAL);
266 for (b = 0; b < planes[p].num_bands; b++) {
267 band = &planes[p].bands[b];
268 x_tiles = IVI_NUM_TILES(band->width, t_width);
269 y_tiles = IVI_NUM_TILES(band->height, t_height);
270 band->num_tiles = x_tiles * y_tiles;
272 av_freep(&band->tiles);
273 band->tiles = av_mallocz(band->num_tiles * sizeof(IVITile));
275 return AVERROR(ENOMEM);
279 /* use the first luma band as reference for motion vectors
281 ref_tile = planes[0].bands[0].tiles;
283 for (y = 0; y < band->height; y += t_height) {
284 for (x = 0; x < band->width; x += t_width) {
287 tile->width = FFMIN(band->width - x, t_width);
288 tile->height = FFMIN(band->height - y, t_height);
289 tile->is_empty = tile->data_size = 0;
290 /* calculate number of macroblocks */
291 tile->num_MBs = IVI_MBs_PER_TILE(tile->width, tile->height,
294 av_freep(&tile->mbs);
295 tile->mbs = av_malloc(tile->num_MBs * sizeof(IVIMbInfo));
297 return AVERROR(ENOMEM);
301 tile->ref_mbs = ref_tile->mbs;
315 int ff_ivi_dec_tile_data_size(GetBitContext *gb)
321 len = get_bits(gb, 8);
323 len = get_bits_long(gb, 24);
326 /* align the bitstream reader on the byte boundary */
332 int ff_ivi_decode_blocks(GetBitContext *gb, IVIBandDesc *band, IVITile *tile)
334 int mbn, blk, num_blocks, num_coeffs, blk_size, scan_pos, run, val,
335 pos, is_intra, mc_type, mv_x, mv_y, col_mask;
336 uint8_t col_flags[8];
337 int32_t prev_dc, trvec[64];
338 uint32_t cbp, sym, lo, hi, quant, buf_offs, q;
340 RVMapDesc *rvmap = band->rv_map;
341 void (*mc_with_delta_func)(int16_t *buf, const int16_t *ref_buf, uint32_t pitch, int mc_type);
342 void (*mc_no_delta_func) (int16_t *buf, const int16_t *ref_buf, uint32_t pitch, int mc_type);
343 const uint16_t *base_tab;
344 const uint8_t *scale_tab;
346 prev_dc = 0; /* init intra prediction for the DC coefficient */
348 blk_size = band->blk_size;
349 col_mask = blk_size - 1; /* column mask for tracking non-zero coeffs */
350 num_blocks = (band->mb_size != blk_size) ? 4 : 1; /* number of blocks per mb */
351 num_coeffs = blk_size * blk_size;
353 mc_with_delta_func = ff_ivi_mc_8x8_delta;
354 mc_no_delta_func = ff_ivi_mc_8x8_no_delta;
356 mc_with_delta_func = ff_ivi_mc_4x4_delta;
357 mc_no_delta_func = ff_ivi_mc_4x4_no_delta;
360 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
361 is_intra = !mb->type;
363 buf_offs = mb->buf_offs;
365 quant = av_clip(band->glob_quant + mb->q_delta, 0, 23);
367 base_tab = is_intra ? band->intra_base : band->inter_base;
368 scale_tab = is_intra ? band->intra_scale : band->inter_scale;
370 quant = scale_tab[quant];
375 if (!band->is_halfpel) {
376 mc_type = 0; /* we have only fullpel vectors */
378 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
380 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
384 for (blk = 0; blk < num_blocks; blk++) {
385 /* adjust block position in the buffer according to its number */
387 buf_offs += blk_size;
388 } else if (blk == 2) {
389 buf_offs -= blk_size;
390 buf_offs += blk_size * band->pitch;
393 if (cbp & 1) { /* block coded ? */
395 memset(trvec, 0, num_coeffs*sizeof(trvec[0])); /* zero transform vector */
396 memset(col_flags, 0, sizeof(col_flags)); /* zero column flags */
398 while (scan_pos <= num_coeffs) {
399 sym = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
400 if (sym == rvmap->eob_sym)
401 break; /* End of block */
403 if (sym == rvmap->esc_sym) { /* Escape - run/val explicitly coded using 3 vlc codes */
404 run = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1) + 1;
405 lo = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
406 hi = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
407 val = IVI_TOSIGNED((hi << 6) | lo); /* merge them and convert into signed val */
410 av_log(NULL, AV_LOG_ERROR, "Invalid sym encountered: %d.\n", sym);
413 run = rvmap->runtab[sym];
414 val = rvmap->valtab[sym];
417 /* de-zigzag and dequantize */
419 if (scan_pos >= num_coeffs)
421 pos = band->scan[scan_pos];
424 av_dlog(NULL, "Val = 0 encountered!\n");
426 q = (base_tab[pos] * quant) >> 9;
428 val = val * q + FFSIGN(val) * (((q ^ 1) - 1) >> 1);
430 col_flags[pos & col_mask] |= !!val; /* track columns containing non-zero coeffs */
433 if (scan_pos >= num_coeffs && sym != rvmap->eob_sym)
434 return -1; /* corrupt block data */
436 /* undoing DC coeff prediction for intra-blocks */
437 if (is_intra && band->is_2d_trans) {
440 col_flags[0] |= !!prev_dc;
443 /* apply inverse transform */
444 band->inv_transform(trvec, band->buf + buf_offs,
445 band->pitch, col_flags);
447 /* apply motion compensation */
449 mc_with_delta_func(band->buf + buf_offs,
450 band->ref_buf + buf_offs + mv_y * band->pitch + mv_x,
451 band->pitch, mc_type);
453 /* block not coded */
454 /* for intra blocks apply the dc slant transform */
455 /* for inter - perform the motion compensation without delta */
456 if (is_intra && band->dc_transform) {
457 band->dc_transform(&prev_dc, band->buf + buf_offs,
458 band->pitch, blk_size);
460 mc_no_delta_func(band->buf + buf_offs,
461 band->ref_buf + buf_offs + mv_y * band->pitch + mv_x,
462 band->pitch, mc_type);
474 void ff_ivi_process_empty_tile(AVCodecContext *avctx, IVIBandDesc *band,
475 IVITile *tile, int32_t mv_scale)
477 int x, y, need_mc, mbn, blk, num_blocks, mv_x, mv_y, mc_type;
478 int offs, mb_offset, row_offset;
479 IVIMbInfo *mb, *ref_mb;
482 void (*mc_no_delta_func)(int16_t *buf, const int16_t *ref_buf, uint32_t pitch,
485 offs = tile->ypos * band->pitch + tile->xpos;
487 ref_mb = tile->ref_mbs;
488 row_offset = band->mb_size * band->pitch;
489 need_mc = 0; /* reset the mc tracking flag */
491 for (y = tile->ypos; y < (tile->ypos + tile->height); y += band->mb_size) {
494 for (x = tile->xpos; x < (tile->xpos + tile->width); x += band->mb_size) {
497 mb->buf_offs = mb_offset;
499 mb->type = 1; /* set the macroblocks type = INTER */
500 mb->cbp = 0; /* all blocks are empty */
502 if (!band->qdelta_present && !band->plane && !band->band_num) {
503 mb->q_delta = band->glob_quant;
508 if (band->inherit_qdelta && ref_mb)
509 mb->q_delta = ref_mb->q_delta;
511 if (band->inherit_mv && ref_mb) {
512 /* motion vector inheritance */
514 mb->mv_x = ivi_scale_mv(ref_mb->mv_x, mv_scale);
515 mb->mv_y = ivi_scale_mv(ref_mb->mv_y, mv_scale);
517 mb->mv_x = ref_mb->mv_x;
518 mb->mv_y = ref_mb->mv_y;
520 need_mc |= mb->mv_x || mb->mv_y; /* tracking non-zero motion vectors */
526 mb_offset += band->mb_size;
531 if (band->inherit_mv && need_mc) { /* apply motion compensation if there is at least one non-zero motion vector */
532 num_blocks = (band->mb_size != band->blk_size) ? 4 : 1; /* number of blocks per mb */
533 mc_no_delta_func = (band->blk_size == 8) ? ff_ivi_mc_8x8_no_delta
534 : ff_ivi_mc_4x4_no_delta;
536 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
539 if (!band->is_halfpel) {
540 mc_type = 0; /* we have only fullpel vectors */
542 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
544 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
547 for (blk = 0; blk < num_blocks; blk++) {
548 /* adjust block position in the buffer according with its number */
549 offs = mb->buf_offs + band->blk_size * ((blk & 1) + !!(blk & 2) * band->pitch);
550 mc_no_delta_func(band->buf + offs,
551 band->ref_buf + offs + mv_y * band->pitch + mv_x,
552 band->pitch, mc_type);
556 /* copy data from the reference tile into the current one */
557 src = band->ref_buf + tile->ypos * band->pitch + tile->xpos;
558 dst = band->buf + tile->ypos * band->pitch + tile->xpos;
559 for (y = 0; y < tile->height; y++) {
560 memcpy(dst, src, tile->width*sizeof(band->buf[0]));
569 uint16_t ivi_calc_band_checksum (IVIBandDesc *band)
572 int16_t *src, checksum;
577 for (y = 0; y < band->height; src += band->pitch, y++)
578 for (x = 0; x < band->width; x++)
584 int ivi_check_band (IVIBandDesc *band, const uint8_t *ref, int pitch)
593 for (y = 0; y < band->height; src += band->pitch, y++) {
594 for (x = 0; x < band->width; x++) {
595 t1 = av_clip(src[x] + 128, 0, 255);
598 av_log(NULL, AV_LOG_ERROR, "Data mismatch: row %d, column %d\n",
599 y / band->blk_size, x / band->blk_size);
610 void ff_ivi_output_plane(IVIPlaneDesc *plane, uint8_t *dst, int dst_pitch)
613 const int16_t *src = plane->bands[0].buf;
614 uint32_t pitch = plane->bands[0].pitch;
619 for (y = 0; y < plane->height; y++) {
620 for (x = 0; x < plane->width; x++)
621 dst[x] = av_clip_uint8(src[x] + 128);
629 * These are 2x8 predefined Huffman codebooks for coding macroblock/block
630 * signals. They are specified using "huffman descriptors" in order to
631 * avoid huge static tables. The decoding tables will be generated at
632 * startup from these descriptors.
634 const IVIHuffDesc ff_ivi_mb_huff_desc[8] = {
635 {8, {0, 4, 5, 4, 4, 4, 6, 6}},
636 {12, {0, 2, 2, 3, 3, 3, 3, 5, 3, 2, 2, 2}},
637 {12, {0, 2, 3, 4, 3, 3, 3, 3, 4, 3, 2, 2}},
638 {12, {0, 3, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2}},
639 {13, {0, 4, 4, 3, 3, 3, 3, 2, 3, 3, 2, 1, 1}},
640 {9, {0, 4, 4, 4, 4, 3, 3, 3, 2}},
641 {10, {0, 4, 4, 4, 4, 3, 3, 2, 2, 2}},
642 {12, {0, 4, 4, 4, 3, 3, 2, 3, 2, 2, 2, 2}}
645 const IVIHuffDesc ff_ivi_blk_huff_desc[8] = {
646 {10, {1, 2, 3, 4, 4, 7, 5, 5, 4, 1}},
647 {11, {2, 3, 4, 4, 4, 7, 5, 4, 3, 3, 2}},
648 {12, {2, 4, 5, 5, 5, 5, 6, 4, 4, 3, 1, 1}},
649 {13, {3, 3, 4, 4, 5, 6, 6, 4, 4, 3, 2, 1, 1}},
650 {11, {3, 4, 4, 5, 5, 5, 6, 5, 4, 2, 2}},
651 {13, {3, 4, 5, 5, 5, 5, 6, 4, 3, 3, 2, 1, 1}},
652 {13, {3, 4, 5, 5, 5, 6, 5, 4, 3, 3, 2, 1, 1}},
653 {9, {3, 4, 4, 5, 5, 5, 6, 5, 5}}
658 * Scan patterns shared between indeo4 and indeo5
660 const uint8_t ff_ivi_vertical_scan_8x8[64] = {
661 0, 8, 16, 24, 32, 40, 48, 56,
662 1, 9, 17, 25, 33, 41, 49, 57,
663 2, 10, 18, 26, 34, 42, 50, 58,
664 3, 11, 19, 27, 35, 43, 51, 59,
665 4, 12, 20, 28, 36, 44, 52, 60,
666 5, 13, 21, 29, 37, 45, 53, 61,
667 6, 14, 22, 30, 38, 46, 54, 62,
668 7, 15, 23, 31, 39, 47, 55, 63
671 const uint8_t ff_ivi_horizontal_scan_8x8[64] = {
672 0, 1, 2, 3, 4, 5, 6, 7,
673 8, 9, 10, 11, 12, 13, 14, 15,
674 16, 17, 18, 19, 20, 21, 22, 23,
675 24, 25, 26, 27, 28, 29, 30, 31,
676 32, 33, 34, 35, 36, 37, 38, 39,
677 40, 41, 42, 43, 44, 45, 46, 47,
678 48, 49, 50, 51, 52, 53, 54, 55,
679 56, 57, 58, 59, 60, 61, 62, 63
682 const uint8_t ff_ivi_direct_scan_4x4[16] = {
683 0, 1, 4, 8, 5, 2, 3, 6, 9, 12, 13, 10, 7, 11, 14, 15
688 * Run-value (RLE) tables.
690 const RVMapDesc ff_ivi_rvmap_tabs[9] = {
695 {1, 1, 0, 1, 1, 0, 1, 1, 2, 2, 1, 1, 1, 1, 3, 3,
696 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 1, 1, 2, 2, 5, 5,
697 1, 1, 3, 3, 1, 1, 6, 6, 1, 2, 1, 2, 7, 7, 1, 1,
698 8, 8, 1, 1, 4, 2, 1, 4, 2, 1, 3, 3, 1, 1, 1, 9,
699 9, 1, 2, 1, 2, 1, 5, 5, 1, 1, 10, 10, 1, 1, 3, 3,
700 2, 2, 1, 1, 11, 11, 6, 4, 4, 1, 6, 1, 2, 1, 2, 12,
701 8, 1, 12, 7, 8, 7, 1, 16, 1, 16, 1, 3, 3, 13, 1, 13,
702 2, 2, 1, 15, 1, 5, 14, 15, 1, 5, 14, 1, 17, 8, 17, 8,
703 1, 4, 4, 2, 2, 1, 25, 25, 24, 24, 1, 3, 1, 3, 1, 8,
704 6, 7, 6, 1, 18, 8, 18, 1, 7, 23, 2, 2, 23, 1, 1, 21,
705 22, 9, 9, 22, 19, 1, 21, 5, 19, 5, 1, 33, 20, 33, 20, 8,
706 4, 4, 1, 32, 2, 2, 8, 3, 32, 26, 3, 1, 7, 7, 26, 6,
707 1, 6, 1, 1, 16, 1, 10, 1, 10, 2, 16, 29, 28, 2, 29, 28,
708 1, 27, 5, 8, 5, 27, 1, 8, 3, 7, 3, 31, 41, 31, 1, 41,
709 6, 1, 6, 7, 4, 4, 1, 1, 2, 1, 2, 11, 34, 30, 11, 1,
710 30, 15, 15, 34, 36, 40, 36, 40, 35, 35, 37, 37, 39, 39, 38, 38},
713 { 1, -1, 0, 2, -2, 0, 3, -3, 1, -1, 4, -4, 5, -5, 1, -1,
714 6, -6, 2, -2, 7, -7, 1, -1, 8, -8, 9, -9, 3, -3, 1, -1,
715 10, -10, 2, -2, 11, -11, 1, -1, 12, 4, -12, -4, 1, -1, 13, -13,
716 1, -1, 14, -14, 2, 5, 15, -2, -5, -15, -3, 3, 16, -16, 17, 1,
717 -1, -17, 6, 18, -6, -18, 2, -2, 19, -19, 1, -1, 20, -20, 4, -4,
718 7, -7, 21, -21, 1, -1, 2, 3, -3, 22, -2, -22, 8, 23, -8, 1,
719 2, -23, -1, 2, -2, -2, 24, 1, -24, -1, 25, 5, -5, 1, -25, -1,
720 9, -9, 26, 1, -26, 3, 1, -1, 27, -3, -1, -27, 1, 3, -1, -3,
721 28, -4, 4, 10, -10, -28, 1, -1, 1, -1, 29, 6, -29, -6, 30, -4,
722 3, 3, -3, -30, 1, 4, -1, 31, -3, 1, 11, -11, -1, -31, 32, -1,
723 -1, 2, -2, 1, 1, -32, 1, 4, -1, -4, 33, -1, 1, 1, -1, 5,
724 5, -5, -33, -1, -12, 12, -5, -7, 1, 1, 7, 34, 4, -4, -1, 4,
725 -34, -4, 35, 36, -2, -35, -2, -36, 2, 13, 2, -1, 1, -13, 1, -1,
726 37, 1, -5, 6, 5, -1, 38, -6, -8, 5, 8, -1, 1, 1, -37, -1,
727 5, 39, -5, -5, 6, -6, -38, -39, -14, 40, 14, 2, 1, 1, -2, -40,
728 -1, -2, 2, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1}
734 {0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 8, 6, 8, 7,
735 7, 9, 9, 10, 10, 11, 11, 1, 12, 1, 12, 13, 13, 16, 14, 16,
736 14, 15, 15, 17, 17, 18, 0, 18, 19, 20, 21, 19, 22, 21, 20, 22,
737 25, 24, 2, 25, 24, 23, 23, 2, 26, 28, 26, 28, 29, 27, 29, 27,
738 33, 33, 1, 32, 1, 3, 32, 30, 36, 3, 36, 30, 31, 31, 35, 34,
739 37, 41, 34, 35, 37, 4, 41, 4, 49, 8, 8, 49, 40, 38, 5, 38,
740 40, 39, 5, 39, 42, 43, 42, 7, 57, 6, 43, 44, 6, 50, 7, 44,
741 57, 48, 50, 48, 45, 45, 46, 47, 51, 46, 47, 58, 1, 51, 58, 1,
742 52, 59, 53, 9, 52, 55, 55, 59, 53, 56, 54, 56, 54, 9, 64, 64,
743 60, 63, 60, 63, 61, 62, 61, 62, 2, 10, 2, 10, 11, 1, 11, 13,
744 12, 1, 12, 13, 16, 16, 8, 8, 14, 3, 3, 15, 14, 15, 4, 4,
745 1, 17, 17, 5, 1, 7, 7, 5, 6, 1, 2, 2, 6, 22, 1, 25,
746 21, 22, 8, 24, 1, 21, 25, 24, 8, 18, 18, 23, 9, 20, 23, 33,
747 29, 33, 20, 1, 19, 1, 29, 36, 9, 36, 19, 41, 28, 57, 32, 3,
748 28, 3, 1, 27, 49, 49, 1, 32, 26, 26, 2, 4, 4, 7, 57, 41,
749 2, 7, 10, 5, 37, 16, 10, 27, 8, 8, 13, 16, 37, 13, 1, 5},
752 {0, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1,
753 -1, 1, -1, 1, -1, 1, -1, 2, 1, -2, -1, 1, -1, 1, 1, -1,
754 -1, 1, -1, 1, -1, 1, 0, -1, 1, 1, 1, -1, 1, -1, -1, -1,
755 1, 1, 2, -1, -1, 1, -1, -2, 1, 1, -1, -1, 1, 1, -1, -1,
756 1, -1, 3, 1, -3, 2, -1, 1, 1, -2, -1, -1, -1, 1, 1, 1,
757 1, 1, -1, -1, -1, 2, -1, -2, 1, 2, -2, -1, 1, 1, 2, -1,
758 -1, 1, -2, -1, 1, 1, -1, 2, 1, 2, -1, 1, -2, -1, -2, -1,
759 -1, 1, 1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 4, -1, -1, -4,
760 1, 1, 1, 2, -1, -1, 1, -1, -1, 1, -1, -1, 1, -2, 1, -1,
761 1, 1, -1, -1, 1, 1, -1, -1, 3, 2, -3, -2, 2, 5, -2, 2,
762 2, -5, -2, -2, -2, 2, -3, 3, 2, 3, -3, 2, -2, -2, 3, -3,
763 6, 2, -2, 3, -6, 3, -3, -3, 3, 7, -4, 4, -3, 2, -7, 2,
764 2, -2, -4, 2, 8, -2, -2, -2, 4, 2, -2, 2, 3, 2, -2, -2,
765 2, 2, -2, -8, -2, 9, -2, 2, -3, -2, 2, -2, 2, 2, 2, 4,
766 -2, -4, 10, 2, 2, -2, -9, -2, 2, -2, 5, 4, -4, 4, -2, 2,
767 -5, -4, -3, 4, 2, -3, 3, -2, -5, 5, 3, 3, -2, -3, -10, -4}
773 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 0, 1, 1, 5, 5,
774 2, 2, 6, 6, 7, 7, 1, 8, 1, 8, 3, 3, 9, 9, 1, 2,
775 2, 1, 4, 10, 4, 10, 11, 11, 1, 5, 12, 12, 1, 5, 13, 13,
776 3, 3, 6, 6, 2, 2, 14, 14, 16, 16, 15, 7, 15, 8, 8, 7,
777 1, 1, 17, 17, 4, 4, 1, 1, 18, 18, 2, 2, 5, 5, 25, 3,
778 9, 3, 25, 9, 19, 24, 19, 24, 1, 21, 20, 1, 21, 22, 20, 22,
779 23, 23, 8, 6, 33, 6, 8, 33, 7, 7, 26, 26, 1, 32, 1, 32,
780 28, 4, 28, 10, 29, 27, 27, 10, 41, 4, 29, 2, 2, 41, 36, 31,
781 49, 31, 34, 30, 34, 36, 30, 35, 1, 49, 11, 5, 35, 11, 1, 3,
782 3, 5, 37, 37, 8, 40, 8, 40, 12, 12, 42, 42, 1, 38, 16, 57,
783 1, 6, 16, 39, 38, 6, 7, 7, 13, 13, 39, 43, 2, 43, 57, 2,
784 50, 9, 44, 9, 50, 4, 15, 48, 44, 4, 1, 15, 48, 14, 14, 1,
785 45, 45, 8, 3, 5, 8, 51, 47, 3, 46, 46, 47, 5, 51, 1, 17,
786 17, 58, 1, 58, 2, 52, 52, 2, 53, 7, 59, 6, 6, 56, 53, 55,
787 7, 55, 1, 54, 59, 56, 54, 10, 1, 10, 4, 60, 1, 60, 8, 4,
788 8, 64, 64, 61, 1, 63, 3, 63, 62, 61, 5, 11, 5, 3, 11, 62},
791 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 0, 3, -3, 1, -1,
792 2, -2, 1, -1, 1, -1, 4, 1, -4, -1, 2, -2, 1, -1, 5, 3,
793 -3, -5, 2, 1, -2, -1, 1, -1, 6, 2, 1, -1, -6, -2, 1, -1,
794 3, -3, 2, -2, 4, -4, 1, -1, 1, -1, 1, 2, -1, 2, -2, -2,
795 7, -7, 1, -1, 3, -3, 8, -8, 1, -1, 5, -5, 3, -3, 1, 4,
796 2, -4, -1, -2, 1, 1, -1, -1, 9, 1, 1, -9, -1, 1, -1, -1,
797 1, -1, 3, -3, 1, 3, -3, -1, 3, -3, 1, -1, 10, 1, -10, -1,
798 1, 4, -1, 2, 1, -1, 1, -2, 1, -4, -1, 6, -6, -1, 1, 1,
799 1, -1, 1, 1, -1, -1, -1, 1, 11, -1, -2, 4, -1, 2, -11, 5,
800 -5, -4, -1, 1, 4, 1, -4, -1, -2, 2, 1, -1, 12, 1, -2, 1,
801 -12, 4, 2, 1, -1, -4, 4, -4, 2, -2, -1, 1, 7, -1, -1, -7,
802 -1, -3, 1, 3, 1, 5, 2, 1, -1, -5, 13, -2, -1, 2, -2, -13,
803 1, -1, 5, 6, 5, -5, 1, 1, -6, 1, -1, -1, -5, -1, 14, 2,
804 -2, 1, -14, -1, 8, 1, -1, -8, 1, 5, 1, 5, -5, 1, -1, 1,
805 -5, -1, 15, 1, -1, -1, -1, 3, -15, -3, 6, 1, 16, -1, 6, -6,
806 -6, 1, -1, 1, -16, 1, 7, -1, 1, -1, -6, -3, 6, -7, 3, -1}
812 {0, 1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6, 6, 7,
813 7, 8, 8, 9, 9, 2, 2, 10, 10, 1, 1, 11, 11, 12, 12, 3,
814 3, 13, 13, 0, 14, 14, 16, 15, 16, 15, 4, 4, 17, 1, 17, 1,
815 5, 5, 18, 18, 2, 2, 6, 6, 8, 19, 7, 8, 7, 19, 20, 20,
816 21, 21, 22, 24, 22, 24, 23, 23, 1, 1, 25, 25, 3, 3, 26, 26,
817 9, 9, 27, 27, 28, 28, 33, 29, 4, 33, 29, 1, 4, 1, 32, 32,
818 2, 2, 31, 10, 30, 10, 30, 31, 34, 34, 5, 5, 36, 36, 35, 41,
819 35, 11, 41, 11, 37, 1, 8, 8, 37, 6, 1, 6, 40, 7, 7, 40,
820 12, 38, 12, 39, 39, 38, 49, 13, 49, 13, 3, 42, 3, 42, 16, 16,
821 43, 43, 14, 14, 1, 1, 44, 15, 44, 15, 2, 2, 57, 48, 50, 48,
822 57, 50, 4, 45, 45, 4, 46, 47, 47, 46, 1, 51, 1, 17, 17, 51,
823 8, 9, 9, 5, 58, 8, 58, 5, 52, 52, 55, 56, 53, 56, 55, 59,
824 59, 53, 54, 1, 6, 54, 7, 7, 6, 1, 2, 3, 2, 3, 64, 60,
825 60, 10, 10, 64, 61, 62, 61, 63, 1, 63, 62, 1, 18, 24, 18, 4,
826 25, 4, 8, 21, 21, 1, 24, 22, 25, 22, 8, 11, 19, 11, 23, 1,
827 20, 23, 19, 20, 5, 12, 5, 1, 16, 2, 12, 13, 2, 13, 1, 16},
830 { 0, 1, -1, 1, -1, 1, -1, 1, -1, 2, -2, 1, -1, 1, -1, 1,
831 -1, 1, -1, 1, -1, 2, -2, 1, -1, 3, -3, 1, -1, 1, -1, 2,
832 -2, 1, -1, 0, 1, -1, 1, 1, -1, -1, 2, -2, 1, 4, -1, -4,
833 2, -2, 1, -1, -3, 3, 2, -2, 2, 1, 2, -2, -2, -1, 1, -1,
834 1, -1, 1, 1, -1, -1, 1, -1, 5, -5, 1, -1, 3, -3, 1, -1,
835 2, -2, 1, -1, 1, -1, 1, 1, 3, -1, -1, 6, -3, -6, -1, 1,
836 4, -4, 1, 2, 1, -2, -1, -1, 1, -1, 3, -3, 1, -1, 1, 1,
837 -1, 2, -1, -2, 1, 7, -3, 3, -1, 3, -7, -3, 1, -3, 3, -1,
838 2, 1, -2, 1, -1, -1, 1, 2, -1, -2, -4, -1, 4, 1, 2, -2,
839 1, -1, -2, 2, 8, -8, -1, 2, 1, -2, -5, 5, 1, -1, -1, 1,
840 -1, 1, 4, -1, 1, -4, -1, -1, 1, 1, 9, 1, -9, 2, -2, -1,
841 -4, 3, -3, -4, -1, 4, 1, 4, 1, -1, 1, -1, 1, 1, -1, 1,
842 -1, -1, -1, 10, 4, 1, 4, -4, -4, -10, 6, 5, -6, -5, 1, -1,
843 1, 3, -3, -1, 1, -1, -1, -1, 11, 1, 1, -11, -2, -2, 2, 5,
844 -2, -5, -5, 2, -2, 12, 2, -2, 2, 2, 5, -3, -2, 3, -2, -12,
845 -2, 2, 2, 2, -5, 3, 5, 13, -3, 7, -3, -3, -7, 3, -13, 3}
851 {0, 1, 1, 1, 2, 2, 1, 3, 3, 1, 1, 1, 4, 4, 1, 5,
852 2, 1, 5, 2, 1, 1, 6, 6, 1, 1, 1, 1, 1, 7, 3, 1,
853 2, 3, 0, 1, 2, 7, 1, 1, 1, 8, 1, 1, 8, 1, 1, 1,
854 9, 1, 9, 1, 2, 1, 1, 2, 1, 1, 10, 4, 1, 10, 1, 4,
855 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 2, 1, 5, 1, 1, 1,
856 2, 5, 1, 11, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
857 2, 1, 6, 1, 6, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 12,
858 3, 1, 12, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1,
859 4, 1, 1, 1, 2, 1, 1, 4, 1, 1, 1, 1, 1, 1, 2, 1,
860 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 5,
861 1, 1, 1, 1, 1, 7, 1, 7, 1, 1, 2, 3, 1, 1, 1, 1,
862 5, 1, 1, 1, 1, 1, 1, 2, 13, 1, 1, 1, 1, 1, 1, 1,
863 1, 1, 1, 1, 1, 1, 1, 1, 13, 2, 1, 1, 4, 1, 1, 1,
864 3, 1, 6, 1, 1, 1, 14, 1, 1, 1, 1, 1, 14, 6, 1, 1,
865 1, 1, 15, 2, 4, 1, 2, 3, 15, 1, 1, 1, 8, 1, 1, 8,
866 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1},
869 { 0, 1, -1, 2, 1, -1, -2, 1, -1, 3, -3, 4, 1, -1, -4, 1,
870 2, 5, -1, -2, -5, 6, 1, -1, -6, 7, -7, 8, -8, 1, 2, 9,
871 3, -2, 0, -9, -3, -1, 10, -10, 11, 1, -11, 12, -1, -12, 13, -13,
872 1, 14, -1, -14, 4, 15, -15, -4, 16, -16, 1, 2, 17, -1, -17, -2,
873 18, -18, 19, -19, 20, 3, -20, 21, -21, -3, 5, 22, 2, -22, -23, 23,
874 -5, -2, 24, 1, -24, -1, 25, -25, 26, -26, -27, 27, 28, 29, -28, -29,
875 6, 30, 2, -31, -2, -30, 31, -6, -32, 32, 33, -33, 34, -35, -34, 1,
876 4, -36, -1, 35, 37, 36, 7, -37, 38, -4, -38, 39, 41, 40, -40, -39,
877 3, 42, -43, -41, -7, -42, 43, -3, 44, -44, 45, -45, 46, 47, 8, -47,
878 -48, -46, 50, -50, 48, 49, 51, -49, 52, -52, 5, -51, -8, -53, 53, 3,
879 -56, 56, 55, 54, -54, 2, 60, -2, -55, 58, 9, -5, 59, 57, -57, -63,
880 -3, -58, -60, -61, 61, -59, -62, -9, 1, 64, 62, 69, -64, 63, 65, -67,
881 -68, 66, -65, 68, -66, -69, 67, -70, -1, 10, 71, -71, 4, 73, 72, 70,
882 6, -76, -3, 74, -78, -74, 1, 78, 80, -72, -75, 76, -1, 3, -73, 79,
883 75, 77, 1, 11, -4, -79, -10, -6, -1, -77, -83, -80, 2, 81, -84, -2,
884 83, -81, 82, -82, 84, -87, -86, 85, -11, -85, 86, -89, 87, -88, 88, 89}
890 {1, 1, 0, 2, 1, 2, 1, 3, 3, 1, 1, 4, 4, 2, 2, 1,
891 1, 5, 5, 6, 1, 6, 1, 7, 7, 3, 3, 2, 8, 2, 8, 1,
892 1, 0, 9, 9, 1, 1, 10, 4, 10, 4, 11, 11, 2, 1, 2, 1,
893 12, 12, 3, 3, 1, 1, 13, 5, 5, 13, 14, 1, 1, 14, 2, 2,
894 6, 6, 15, 1, 1, 15, 16, 4, 7, 16, 4, 7, 1, 1, 3, 3,
895 8, 8, 2, 2, 1, 1, 17, 17, 1, 1, 18, 18, 5, 5, 2, 2,
896 1, 1, 9, 19, 9, 19, 20, 3, 3, 20, 1, 10, 21, 1, 10, 4,
897 4, 21, 22, 6, 6, 22, 1, 1, 23, 24, 2, 2, 23, 24, 11, 1,
898 1, 11, 7, 25, 7, 1, 1, 25, 8, 8, 3, 26, 3, 1, 12, 2,
899 2, 26, 1, 12, 5, 5, 27, 4, 1, 4, 1, 27, 28, 1, 28, 13,
900 1, 13, 2, 29, 2, 1, 32, 6, 1, 30, 14, 29, 14, 6, 3, 31,
901 3, 1, 30, 1, 32, 31, 33, 9, 33, 1, 1, 7, 9, 7, 2, 2,
902 1, 1, 4, 36, 34, 4, 5, 10, 10, 5, 34, 1, 1, 35, 8, 8,
903 36, 3, 35, 1, 15, 3, 2, 1, 16, 15, 16, 2, 37, 1, 37, 1,
904 1, 1, 6, 6, 38, 1, 38, 11, 1, 39, 39, 40, 11, 2, 41, 4,
905 40, 1, 2, 4, 1, 1, 1, 41, 3, 1, 3, 1, 5, 7, 5, 7},
908 { 1, -1, 0, 1, 2, -1, -2, 1, -1, 3, -3, 1, -1, 2, -2, 4,
909 -4, 1, -1, 1, 5, -1, -5, 1, -1, 2, -2, 3, 1, -3, -1, 6,
910 -6, 0, 1, -1, 7, -7, 1, 2, -1, -2, 1, -1, 4, 8, -4, -8,
911 1, -1, 3, -3, 9, -9, 1, 2, -2, -1, 1, 10, -10, -1, 5, -5,
912 2, -2, 1, 11, -11, -1, 1, 3, 2, -1, -3, -2, 12, -12, 4, -4,
913 2, -2, -6, 6, 13, -13, 1, -1, 14, -14, 1, -1, 3, -3, 7, -7,
914 15, -15, 2, 1, -2, -1, 1, 5, -5, -1, -16, 2, 1, 16, -2, 4,
915 -4, -1, 1, 3, -3, -1, 17, -17, 1, 1, -8, 8, -1, -1, 2, 18,
916 -18, -2, 3, 1, -3, 19, -19, -1, 3, -3, 6, 1, -6, 20, 2, 9,
917 -9, -1, -20, -2, 4, -4, 1, -5, 21, 5, -21, -1, 1, -22, -1, 2,
918 22, -2, 10, 1, -10, 23, 1, 4, -23, 1, 2, -1, -2, -4, -7, 1,
919 7, -24, -1, 24, -1, -1, 1, 3, -1, -25, 25, 4, -3, -4, 11, -11,
920 26, -26, 6, 1, 1, -6, -5, -3, 3, 5, -1, -27, 27, 1, 4, -4,
921 -1, -8, -1, 28, 2, 8, -12, -28, -2, -2, 2, 12, -1, 29, 1, -29,
922 30, -30, 5, -5, 1, -31, -1, 3, 31, -1, 1, 1, -3, -13, 1, -7,
923 -1, -32, 13, 7, 32, 33, -33, -1, -9, -34, 9, 34, -6, 5, 6, -5}
929 {1, 1, 0, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 0, 2, 2,
930 4, 1, 4, 1, 1, 1, 5, 5, 1, 1, 6, 6, 2, 2, 1, 1,
931 3, 3, 7, 7, 1, 1, 8, 8, 1, 1, 2, 2, 1, 9, 1, 9,
932 4, 4, 10, 1, 1, 10, 1, 1, 11, 11, 3, 3, 1, 2, 1, 2,
933 1, 1, 12, 12, 5, 5, 1, 1, 13, 1, 1, 13, 2, 2, 1, 1,
934 6, 6, 1, 1, 4, 14, 4, 14, 3, 1, 3, 1, 1, 1, 15, 7,
935 15, 2, 2, 7, 1, 1, 1, 8, 1, 8, 16, 16, 1, 1, 1, 1,
936 2, 1, 1, 2, 1, 1, 3, 5, 5, 3, 4, 1, 1, 4, 1, 1,
937 17, 17, 9, 1, 1, 9, 2, 2, 1, 1, 10, 10, 1, 6, 1, 1,
938 6, 18, 1, 1, 18, 1, 1, 1, 2, 2, 3, 1, 3, 1, 1, 1,
939 4, 1, 19, 1, 19, 7, 1, 1, 20, 1, 4, 20, 1, 7, 11, 2,
940 1, 11, 21, 2, 8, 5, 1, 8, 1, 5, 21, 1, 1, 1, 22, 1,
941 1, 22, 1, 1, 3, 3, 1, 23, 2, 12, 24, 1, 1, 2, 1, 1,
942 12, 23, 1, 1, 24, 1, 1, 1, 4, 1, 1, 1, 2, 1, 6, 6,
943 4, 2, 1, 1, 1, 1, 1, 1, 1, 14, 13, 3, 1, 25, 9, 25,
944 14, 1, 9, 3, 13, 1, 1, 1, 1, 1, 10, 1, 1, 2, 10, 2},
947 {-20, -1, 0, 2, -2, 1, -1, 3, -3, 1, -1, 4, -4, 0, 2, -2,
948 1, 5, -1, -5, 6, -6, 1, -1, 7, -7, 1, -1, 3, -3, 8, -8,
949 2, -2, 1, -1, 9, -9, 1, -1, 10, -10, 4, -4, 11, 1, -11, -1,
950 2, -2, 1, 12, -12, -1, 13, -13, 1, -1, 3, -3, 14, 5, -14, -5,
951 -15, 15, -1, 1, 2, -2, 16, -16, 1, 17, -17, -1, 6, -6, 18, -18,
952 2, -2, -19, 19, -3, 1, 3, -1, 4, 20, -4, 1, -21, 21, 1, 2,
953 -1, -7, 7, -2, 22, -22, 23, 2, -23, -2, 1, -1, -24, 24, -25, 25,
954 -8, -26, 26, 8, -27, 27, 5, 3, -3, -5, -4, 28, -28, 4, 29, -29,
955 1, -1, -2, -30, 30, 2, 9, -9, -31, 31, 2, -2, -32, 3, 32, -33,
956 -3, 1, 33, -34, -1, 34, -35, 35, -10, 10, -6, 36, 6, -36, 37, -37,
957 -5, 38, 1, -38, -1, 3, 39, -39, -1, 40, 5, 1, -40, -3, 2, -11,
958 -41, -2, 1, 11, -3, -4, 41, 3, 42, 4, -1, -43, -42, 43, 1, -44,
959 45, -1, 44, -45, -7, 7, -46, 1, -12, 2, 1, -47, 46, 12, 47, 48,
960 -2, -1, -48, 49, -1, -50, -49, 50, -6, -51, 51, 52, -13, 53, -4, 4,
961 6, 13, -53, -52, -54, 55, 54, -55, -56, -2, 2, -8, 56, 1, -3, -1,
962 2, 58, 3, 8, -2, 57, -58, -60, -59, -57, -3, 60, 59, -14, 3, 14}
968 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 5, 5, 1, 1, 6,
969 6, 2, 2, 7, 7, 8, 8, 1, 1, 3, 3, 9, 9, 10, 10, 1,
970 1, 2, 2, 4, 4, 11, 0, 11, 12, 12, 13, 13, 1, 1, 5, 5,
971 14, 14, 15, 16, 15, 16, 3, 3, 1, 6, 1, 6, 2, 2, 7, 7,
972 8, 8, 17, 17, 1, 1, 4, 4, 18, 18, 2, 2, 1, 19, 1, 20,
973 19, 20, 21, 21, 3, 3, 22, 22, 5, 5, 24, 1, 1, 23, 9, 23,
974 24, 9, 2, 2, 10, 1, 1, 10, 6, 6, 25, 4, 4, 25, 7, 7,
975 26, 8, 1, 8, 3, 1, 26, 3, 11, 11, 27, 27, 2, 28, 1, 2,
976 28, 1, 12, 12, 5, 5, 29, 13, 13, 29, 32, 1, 1, 33, 31, 30,
977 32, 4, 30, 33, 4, 31, 3, 14, 1, 1, 3, 34, 34, 2, 2, 14,
978 6, 6, 35, 36, 35, 36, 1, 15, 1, 16, 16, 15, 7, 9, 7, 9,
979 37, 8, 8, 37, 1, 1, 39, 2, 38, 39, 2, 40, 5, 38, 40, 5,
980 3, 3, 4, 4, 10, 10, 1, 1, 1, 1, 41, 2, 41, 2, 6, 6,
981 1, 1, 11, 42, 11, 43, 3, 42, 3, 17, 4, 43, 1, 17, 7, 1,
982 8, 44, 4, 7, 44, 5, 8, 2, 5, 1, 2, 48, 45, 1, 12, 45,
983 12, 48, 13, 13, 1, 9, 9, 46, 1, 46, 47, 47, 49, 18, 18, 49},
986 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 1, -1, 3, -3, 1,
987 -1, -2, 2, 1, -1, 1, -1, 4, -4, -2, 2, 1, -1, 1, -1, 5,
988 -5, -3, 3, 2, -2, 1, 0, -1, 1, -1, 1, -1, 6, -6, 2, -2,
989 1, -1, 1, 1, -1, -1, -3, 3, 7, 2, -7, -2, -4, 4, 2, -2,
990 2, -2, 1, -1, 8, -8, 3, -3, 1, -1, -5, 5, 9, 1, -9, 1,
991 -1, -1, 1, -1, -4, 4, 1, -1, 3, -3, 1, -10, 10, 1, 2, -1,
992 -1, -2, 6, -6, 2, 11, -11, -2, 3, -3, 1, -4, 4, -1, 3, -3,
993 1, 3, 12, -3, -5, -12, -1, 5, 2, -2, 1, -1, -7, 1, 13, 7,
994 -1, -13, 2, -2, 4, -4, 1, 2, -2, -1, 1, 14, -14, 1, 1, 1,
995 -1, -5, -1, -1, 5, -1, -6, 2, -15, 15, 6, 1, -1, -8, 8, -2,
996 -4, 4, 1, 1, -1, -1, 16, 2, -16, -2, 2, -2, 4, 3, -4, -3,
997 -1, -4, 4, 1, -17, 17, -1, -9, 1, 1, 9, 1, -5, -1, -1, 5,
998 -7, 7, 6, -6, 3, -3, 18, -18, 19, -19, 1, -10, -1, 10, -5, 5,
999 20, -20, -3, 1, 3, 1, 8, -1, -8, 2, 7, -1, -21, -2, 5, 21,
1000 5, -1, -7, -5, 1, -6, -5, -11, 6, 22, 11, 1, 1, -22, -3, -1,
1001 3, -1, 3, -3, -23, 4, -4, 1, 23, -1, 1, -1, 1, -2, 2, -1}
1007 {1, 1, 1, 1, 0, 2, 2, 1, 1, 3, 3, 0, 1, 1, 2, 2,
1008 4, 4, 1, 1, 5, 5, 1, 1, 2, 2, 3, 3, 6, 6, 1, 1,
1009 7, 7, 8, 1, 8, 2, 2, 1, 4, 4, 1, 3, 1, 3, 9, 9,
1010 2, 2, 1, 5, 1, 5, 10, 10, 1, 1, 11, 11, 3, 6, 3, 4,
1011 4, 6, 2, 2, 1, 12, 1, 12, 7, 13, 7, 13, 1, 1, 8, 8,
1012 2, 2, 14, 14, 16, 15, 16, 5, 5, 1, 3, 15, 1, 3, 4, 4,
1013 1, 1, 17, 17, 2, 2, 6, 6, 1, 18, 1, 18, 22, 21, 22, 21,
1014 25, 24, 25, 19, 9, 20, 9, 23, 19, 24, 20, 3, 23, 7, 3, 1,
1015 1, 7, 28, 26, 29, 5, 28, 26, 5, 8, 29, 4, 8, 27, 2, 2,
1016 4, 27, 1, 1, 10, 36, 10, 33, 33, 36, 30, 1, 32, 32, 1, 30,
1017 6, 31, 31, 35, 3, 6, 11, 11, 3, 2, 35, 2, 34, 1, 34, 1,
1018 37, 37, 12, 7, 12, 5, 41, 5, 4, 7, 1, 8, 13, 4, 1, 41,
1019 13, 38, 8, 38, 9, 1, 40, 40, 9, 1, 39, 2, 2, 49, 39, 42,
1020 3, 3, 14, 16, 49, 14, 16, 42, 43, 43, 6, 6, 15, 1, 1, 15,
1021 44, 44, 1, 1, 50, 48, 4, 5, 4, 7, 5, 2, 10, 10, 48, 7,
1022 50, 45, 2, 1, 45, 8, 8, 1, 46, 46, 3, 47, 47, 3, 1, 1},
1025 { 1, -1, 2, -2, 0, 1, -1, 3, -3, 1, -1, 0, 4, -4, 2, -2,
1026 1, -1, 5, -5, 1, -1, 6, -6, 3, -3, 2, -2, 1, -1, 7, -7,
1027 1, -1, 1, 8, -1, 4, -4, -8, 2, -2, 9, 3, -9, -3, 1, -1,
1028 5, -5, 10, 2, -10, -2, 1, -1, 11, -11, 1, -1, -4, 2, 4, 3,
1029 -3, -2, 6, -6, 12, 1, -12, -1, 2, 1, -2, -1, 13, -13, 2, -2,
1030 7, -7, 1, -1, 1, 1, -1, 3, -3, 14, 5, -1, -14, -5, 4, -4,
1031 15, -15, 1, -1, 8, -8, -3, 3, 16, 1, -16, -1, 1, 1, -1, -1,
1032 1, 1, -1, 1, 2, 1, -2, 1, -1, -1, -1, 6, -1, 3, -6, 17,
1033 -17, -3, 1, 1, 1, 4, -1, -1, -4, 3, -1, 5, -3, -1, -9, 9,
1034 -5, 1, 18, -18, 2, 1, -2, 1, -1, -1, 1, 19, -1, 1, -19, -1,
1035 4, 1, -1, 1, 7, -4, -2, 2, -7, 10, -1, -10, 1, 20, -1, -20,
1036 1, -1, 2, 4, -2, 5, 1, -5, 6, -4, 21, 4, 2, -6, -21, -1,
1037 -2, 1, -4, -1, -3, 22, -1, 1, 3, -22, -1, 11, -11, 1, 1, 1,
1038 8, -8, 2, 2, -1, -2, -2, -1, 1, -1, -5, 5, 2, 23, -23, -2,
1039 1, -1, 24, -24, -1, -1, 7, 6, -7, 5, -6, 12, -3, 3, 1, -5,
1040 1, 1, -12, 25, -1, -5, 5, -25, -1, 1, 9, 1, -1, -9, 26, -26}