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 ALT_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) {
264 for (b = 0; b < planes[p].num_bands; b++) {
265 band = &planes[p].bands[b];
266 x_tiles = IVI_NUM_TILES(band->width, t_width);
267 y_tiles = IVI_NUM_TILES(band->height, t_height);
268 band->num_tiles = x_tiles * y_tiles;
270 av_freep(&band->tiles);
271 band->tiles = av_mallocz(band->num_tiles * sizeof(IVITile));
273 return AVERROR(ENOMEM);
277 /* use the first luma band as reference for motion vectors
279 ref_tile = planes[0].bands[0].tiles;
281 for (y = 0; y < band->height; y += t_height) {
282 for (x = 0; x < band->width; x += t_width) {
285 tile->width = FFMIN(band->width - x, t_width);
286 tile->height = FFMIN(band->height - y, t_height);
287 tile->is_empty = tile->data_size = 0;
288 /* calculate number of macroblocks */
289 tile->num_MBs = IVI_MBs_PER_TILE(tile->width, tile->height,
292 av_freep(&tile->mbs);
293 tile->mbs = av_malloc(tile->num_MBs * sizeof(IVIMbInfo));
295 return AVERROR(ENOMEM);
299 tile->ref_mbs = ref_tile->mbs;
313 int ff_ivi_dec_tile_data_size(GetBitContext *gb)
319 len = get_bits(gb, 8);
321 len = get_bits_long(gb, 24);
324 /* align the bitstream reader on the byte boundary */
330 int ff_ivi_decode_blocks(GetBitContext *gb, IVIBandDesc *band, IVITile *tile)
332 int mbn, blk, num_blocks, num_coeffs, blk_size, scan_pos, run, val,
333 pos, is_intra, mc_type, mv_x, mv_y, col_mask;
334 uint8_t col_flags[8];
335 int32_t prev_dc, trvec[64];
336 uint32_t cbp, sym, lo, hi, quant, buf_offs, q;
338 RVMapDesc *rvmap = band->rv_map;
339 void (*mc_with_delta_func)(int16_t *buf, const int16_t *ref_buf, uint32_t pitch, int mc_type);
340 void (*mc_no_delta_func) (int16_t *buf, const int16_t *ref_buf, uint32_t pitch, int mc_type);
341 const uint16_t *base_tab;
342 const uint8_t *scale_tab;
344 prev_dc = 0; /* init intra prediction for the DC coefficient */
346 blk_size = band->blk_size;
347 col_mask = blk_size - 1; /* column mask for tracking non-zero coeffs */
348 num_blocks = (band->mb_size != blk_size) ? 4 : 1; /* number of blocks per mb */
349 num_coeffs = blk_size * blk_size;
351 mc_with_delta_func = ff_ivi_mc_8x8_delta;
352 mc_no_delta_func = ff_ivi_mc_8x8_no_delta;
354 mc_with_delta_func = ff_ivi_mc_4x4_delta;
355 mc_no_delta_func = ff_ivi_mc_4x4_no_delta;
358 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
359 is_intra = !mb->type;
361 buf_offs = mb->buf_offs;
363 quant = av_clip(band->glob_quant + mb->q_delta, 0, 23);
365 base_tab = is_intra ? band->intra_base : band->inter_base;
366 scale_tab = is_intra ? band->intra_scale : band->inter_scale;
368 quant = scale_tab[quant];
373 if (!band->is_halfpel) {
374 mc_type = 0; /* we have only fullpel vectors */
376 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
378 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
382 for (blk = 0; blk < num_blocks; blk++) {
383 /* adjust block position in the buffer according to its number */
385 buf_offs += blk_size;
386 } else if (blk == 2) {
387 buf_offs -= blk_size;
388 buf_offs += blk_size * band->pitch;
391 if (cbp & 1) { /* block coded ? */
393 memset(trvec, 0, num_coeffs*sizeof(trvec[0])); /* zero transform vector */
394 memset(col_flags, 0, sizeof(col_flags)); /* zero column flags */
396 while (scan_pos <= num_coeffs) {
397 sym = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
398 if (sym == rvmap->eob_sym)
399 break; /* End of block */
401 if (sym == rvmap->esc_sym) { /* Escape - run/val explicitly coded using 3 vlc codes */
402 run = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1) + 1;
403 lo = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
404 hi = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
405 val = IVI_TOSIGNED((hi << 6) | lo); /* merge them and convert into signed val */
408 av_log(NULL, AV_LOG_ERROR, "Invalid sym encountered: %d.\n", sym);
411 run = rvmap->runtab[sym];
412 val = rvmap->valtab[sym];
415 /* de-zigzag and dequantize */
417 if (scan_pos >= num_coeffs)
419 pos = band->scan[scan_pos];
421 if (IVI_DEBUG && !val)
422 av_log(NULL, AV_LOG_ERROR, "Val = 0 encountered!\n");
424 q = (base_tab[pos] * quant) >> 9;
426 val = val * q + FFSIGN(val) * (((q ^ 1) - 1) >> 1);
428 col_flags[pos & col_mask] |= !!val; /* track columns containing non-zero coeffs */
431 if (scan_pos >= num_coeffs && sym != rvmap->eob_sym)
432 return -1; /* corrupt block data */
434 /* undoing DC coeff prediction for intra-blocks */
435 if (is_intra && band->is_2d_trans) {
438 col_flags[0] |= !!prev_dc;
441 /* apply inverse transform */
442 band->inv_transform(trvec, band->buf + buf_offs,
443 band->pitch, col_flags);
445 /* apply motion compensation */
447 mc_with_delta_func(band->buf + buf_offs,
448 band->ref_buf + buf_offs + mv_y * band->pitch + mv_x,
449 band->pitch, mc_type);
451 /* block not coded */
452 /* for intra blocks apply the dc slant transform */
453 /* for inter - perform the motion compensation without delta */
454 if (is_intra && band->dc_transform) {
455 band->dc_transform(&prev_dc, band->buf + buf_offs,
456 band->pitch, blk_size);
458 mc_no_delta_func(band->buf + buf_offs,
459 band->ref_buf + buf_offs + mv_y * band->pitch + mv_x,
460 band->pitch, mc_type);
472 void ff_ivi_process_empty_tile(AVCodecContext *avctx, IVIBandDesc *band,
473 IVITile *tile, int32_t mv_scale)
475 int x, y, need_mc, mbn, blk, num_blocks, mv_x, mv_y, mc_type;
476 int offs, mb_offset, row_offset;
477 IVIMbInfo *mb, *ref_mb;
480 void (*mc_no_delta_func)(int16_t *buf, const int16_t *ref_buf, uint32_t pitch,
483 offs = tile->ypos * band->pitch + tile->xpos;
485 ref_mb = tile->ref_mbs;
486 row_offset = band->mb_size * band->pitch;
487 need_mc = 0; /* reset the mc tracking flag */
489 for (y = tile->ypos; y < (tile->ypos + tile->height); y += band->mb_size) {
492 for (x = tile->xpos; x < (tile->xpos + tile->width); x += band->mb_size) {
495 mb->buf_offs = mb_offset;
497 mb->type = 1; /* set the macroblocks type = INTER */
498 mb->cbp = 0; /* all blocks are empty */
500 if (!band->qdelta_present && !band->plane && !band->band_num) {
501 mb->q_delta = band->glob_quant;
506 if (band->inherit_qdelta && ref_mb)
507 mb->q_delta = ref_mb->q_delta;
509 if (band->inherit_mv) {
510 /* motion vector inheritance */
512 mb->mv_x = ivi_scale_mv(ref_mb->mv_x, mv_scale);
513 mb->mv_y = ivi_scale_mv(ref_mb->mv_y, mv_scale);
515 mb->mv_x = ref_mb->mv_x;
516 mb->mv_y = ref_mb->mv_y;
518 need_mc |= mb->mv_x || mb->mv_y; /* tracking non-zero motion vectors */
524 mb_offset += band->mb_size;
529 if (band->inherit_mv && need_mc) { /* apply motion compensation if there is at least one non-zero motion vector */
530 num_blocks = (band->mb_size != band->blk_size) ? 4 : 1; /* number of blocks per mb */
531 mc_no_delta_func = (band->blk_size == 8) ? ff_ivi_mc_8x8_no_delta
532 : ff_ivi_mc_4x4_no_delta;
534 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
537 if (!band->is_halfpel) {
538 mc_type = 0; /* we have only fullpel vectors */
540 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
542 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
545 for (blk = 0; blk < num_blocks; blk++) {
546 /* adjust block position in the buffer according with its number */
547 offs = mb->buf_offs + band->blk_size * ((blk & 1) + !!(blk & 2) * band->pitch);
548 mc_no_delta_func(band->buf + offs,
549 band->ref_buf + offs + mv_y * band->pitch + mv_x,
550 band->pitch, mc_type);
554 /* copy data from the reference tile into the current one */
555 src = band->ref_buf + tile->ypos * band->pitch + tile->xpos;
556 dst = band->buf + tile->ypos * band->pitch + tile->xpos;
557 for (y = 0; y < tile->height; y++) {
558 memcpy(dst, src, tile->width*sizeof(band->buf[0]));
567 uint16_t ivi_calc_band_checksum (IVIBandDesc *band)
570 int16_t *src, checksum;
575 for (y = 0; y < band->height; src += band->pitch, y++)
576 for (x = 0; x < band->width; x++)
582 int ivi_check_band (IVIBandDesc *band, const uint8_t *ref, int pitch)
591 for (y = 0; y < band->height; src += band->pitch, y++) {
592 for (x = 0; x < band->width; x++) {
593 t1 = av_clip(src[x] + 128, 0, 255);
596 av_log(NULL, AV_LOG_ERROR, "Data mismatch: row %d, column %d\n",
597 y / band->blk_size, x / band->blk_size);
608 void ff_ivi_output_plane(IVIPlaneDesc *plane, uint8_t *dst, int dst_pitch)
611 const int16_t *src = plane->bands[0].buf;
612 uint32_t pitch = plane->bands[0].pitch;
614 for (y = 0; y < plane->height; y++) {
615 for (x = 0; x < plane->width; x++)
616 dst[x] = av_clip_uint8(src[x] + 128);
624 * These are 2x8 predefined Huffman codebooks for coding macroblock/block
625 * signals. They are specified using "huffman descriptors" in order to
626 * avoid huge static tables. The decoding tables will be generated at
627 * startup from these descriptors.
629 const IVIHuffDesc ff_ivi_mb_huff_desc[8] = {
630 {8, {0, 4, 5, 4, 4, 4, 6, 6}},
631 {12, {0, 2, 2, 3, 3, 3, 3, 5, 3, 2, 2, 2}},
632 {12, {0, 2, 3, 4, 3, 3, 3, 3, 4, 3, 2, 2}},
633 {12, {0, 3, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2}},
634 {13, {0, 4, 4, 3, 3, 3, 3, 2, 3, 3, 2, 1, 1}},
635 {9, {0, 4, 4, 4, 4, 3, 3, 3, 2}},
636 {10, {0, 4, 4, 4, 4, 3, 3, 2, 2, 2}},
637 {12, {0, 4, 4, 4, 3, 3, 2, 3, 2, 2, 2, 2}}
640 const IVIHuffDesc ff_ivi_blk_huff_desc[8] = {
641 {10, {1, 2, 3, 4, 4, 7, 5, 5, 4, 1}},
642 {11, {2, 3, 4, 4, 4, 7, 5, 4, 3, 3, 2}},
643 {12, {2, 4, 5, 5, 5, 5, 6, 4, 4, 3, 1, 1}},
644 {13, {3, 3, 4, 4, 5, 6, 6, 4, 4, 3, 2, 1, 1}},
645 {11, {3, 4, 4, 5, 5, 5, 6, 5, 4, 2, 2}},
646 {13, {3, 4, 5, 5, 5, 5, 6, 4, 3, 3, 2, 1, 1}},
647 {13, {3, 4, 5, 5, 5, 6, 5, 4, 3, 3, 2, 1, 1}},
648 {9, {3, 4, 4, 5, 5, 5, 6, 5, 5}}
653 * Scan patterns shared between indeo4 and indeo5
655 const uint8_t ff_ivi_vertical_scan_8x8[64] = {
656 0, 8, 16, 24, 32, 40, 48, 56,
657 1, 9, 17, 25, 33, 41, 49, 57,
658 2, 10, 18, 26, 34, 42, 50, 58,
659 3, 11, 19, 27, 35, 43, 51, 59,
660 4, 12, 20, 28, 36, 44, 52, 60,
661 5, 13, 21, 29, 37, 45, 53, 61,
662 6, 14, 22, 30, 38, 46, 54, 62,
663 7, 15, 23, 31, 39, 47, 55, 63
666 const uint8_t ff_ivi_horizontal_scan_8x8[64] = {
667 0, 1, 2, 3, 4, 5, 6, 7,
668 8, 9, 10, 11, 12, 13, 14, 15,
669 16, 17, 18, 19, 20, 21, 22, 23,
670 24, 25, 26, 27, 28, 29, 30, 31,
671 32, 33, 34, 35, 36, 37, 38, 39,
672 40, 41, 42, 43, 44, 45, 46, 47,
673 48, 49, 50, 51, 52, 53, 54, 55,
674 56, 57, 58, 59, 60, 61, 62, 63
677 const uint8_t ff_ivi_direct_scan_4x4[16] = {
678 0, 1, 4, 8, 5, 2, 3, 6, 9, 12, 13, 10, 7, 11, 14, 15
683 * Run-value (RLE) tables.
685 const RVMapDesc ff_ivi_rvmap_tabs[9] = {
690 {1, 1, 0, 1, 1, 0, 1, 1, 2, 2, 1, 1, 1, 1, 3, 3,
691 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 1, 1, 2, 2, 5, 5,
692 1, 1, 3, 3, 1, 1, 6, 6, 1, 2, 1, 2, 7, 7, 1, 1,
693 8, 8, 1, 1, 4, 2, 1, 4, 2, 1, 3, 3, 1, 1, 1, 9,
694 9, 1, 2, 1, 2, 1, 5, 5, 1, 1, 10, 10, 1, 1, 3, 3,
695 2, 2, 1, 1, 11, 11, 6, 4, 4, 1, 6, 1, 2, 1, 2, 12,
696 8, 1, 12, 7, 8, 7, 1, 16, 1, 16, 1, 3, 3, 13, 1, 13,
697 2, 2, 1, 15, 1, 5, 14, 15, 1, 5, 14, 1, 17, 8, 17, 8,
698 1, 4, 4, 2, 2, 1, 25, 25, 24, 24, 1, 3, 1, 3, 1, 8,
699 6, 7, 6, 1, 18, 8, 18, 1, 7, 23, 2, 2, 23, 1, 1, 21,
700 22, 9, 9, 22, 19, 1, 21, 5, 19, 5, 1, 33, 20, 33, 20, 8,
701 4, 4, 1, 32, 2, 2, 8, 3, 32, 26, 3, 1, 7, 7, 26, 6,
702 1, 6, 1, 1, 16, 1, 10, 1, 10, 2, 16, 29, 28, 2, 29, 28,
703 1, 27, 5, 8, 5, 27, 1, 8, 3, 7, 3, 31, 41, 31, 1, 41,
704 6, 1, 6, 7, 4, 4, 1, 1, 2, 1, 2, 11, 34, 30, 11, 1,
705 30, 15, 15, 34, 36, 40, 36, 40, 35, 35, 37, 37, 39, 39, 38, 38},
708 { 1, -1, 0, 2, -2, 0, 3, -3, 1, -1, 4, -4, 5, -5, 1, -1,
709 6, -6, 2, -2, 7, -7, 1, -1, 8, -8, 9, -9, 3, -3, 1, -1,
710 10, -10, 2, -2, 11, -11, 1, -1, 12, 4, -12, -4, 1, -1, 13, -13,
711 1, -1, 14, -14, 2, 5, 15, -2, -5, -15, -3, 3, 16, -16, 17, 1,
712 -1, -17, 6, 18, -6, -18, 2, -2, 19, -19, 1, -1, 20, -20, 4, -4,
713 7, -7, 21, -21, 1, -1, 2, 3, -3, 22, -2, -22, 8, 23, -8, 1,
714 2, -23, -1, 2, -2, -2, 24, 1, -24, -1, 25, 5, -5, 1, -25, -1,
715 9, -9, 26, 1, -26, 3, 1, -1, 27, -3, -1, -27, 1, 3, -1, -3,
716 28, -4, 4, 10, -10, -28, 1, -1, 1, -1, 29, 6, -29, -6, 30, -4,
717 3, 3, -3, -30, 1, 4, -1, 31, -3, 1, 11, -11, -1, -31, 32, -1,
718 -1, 2, -2, 1, 1, -32, 1, 4, -1, -4, 33, -1, 1, 1, -1, 5,
719 5, -5, -33, -1, -12, 12, -5, -7, 1, 1, 7, 34, 4, -4, -1, 4,
720 -34, -4, 35, 36, -2, -35, -2, -36, 2, 13, 2, -1, 1, -13, 1, -1,
721 37, 1, -5, 6, 5, -1, 38, -6, -8, 5, 8, -1, 1, 1, -37, -1,
722 5, 39, -5, -5, 6, -6, -38, -39, -14, 40, 14, 2, 1, 1, -2, -40,
723 -1, -2, 2, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1}
729 {0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 8, 6, 8, 7,
730 7, 9, 9, 10, 10, 11, 11, 1, 12, 1, 12, 13, 13, 16, 14, 16,
731 14, 15, 15, 17, 17, 18, 0, 18, 19, 20, 21, 19, 22, 21, 20, 22,
732 25, 24, 2, 25, 24, 23, 23, 2, 26, 28, 26, 28, 29, 27, 29, 27,
733 33, 33, 1, 32, 1, 3, 32, 30, 36, 3, 36, 30, 31, 31, 35, 34,
734 37, 41, 34, 35, 37, 4, 41, 4, 49, 8, 8, 49, 40, 38, 5, 38,
735 40, 39, 5, 39, 42, 43, 42, 7, 57, 6, 43, 44, 6, 50, 7, 44,
736 57, 48, 50, 48, 45, 45, 46, 47, 51, 46, 47, 58, 1, 51, 58, 1,
737 52, 59, 53, 9, 52, 55, 55, 59, 53, 56, 54, 56, 54, 9, 64, 64,
738 60, 63, 60, 63, 61, 62, 61, 62, 2, 10, 2, 10, 11, 1, 11, 13,
739 12, 1, 12, 13, 16, 16, 8, 8, 14, 3, 3, 15, 14, 15, 4, 4,
740 1, 17, 17, 5, 1, 7, 7, 5, 6, 1, 2, 2, 6, 22, 1, 25,
741 21, 22, 8, 24, 1, 21, 25, 24, 8, 18, 18, 23, 9, 20, 23, 33,
742 29, 33, 20, 1, 19, 1, 29, 36, 9, 36, 19, 41, 28, 57, 32, 3,
743 28, 3, 1, 27, 49, 49, 1, 32, 26, 26, 2, 4, 4, 7, 57, 41,
744 2, 7, 10, 5, 37, 16, 10, 27, 8, 8, 13, 16, 37, 13, 1, 5},
747 {0, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1,
748 -1, 1, -1, 1, -1, 1, -1, 2, 1, -2, -1, 1, -1, 1, 1, -1,
749 -1, 1, -1, 1, -1, 1, 0, -1, 1, 1, 1, -1, 1, -1, -1, -1,
750 1, 1, 2, -1, -1, 1, -1, -2, 1, 1, -1, -1, 1, 1, -1, -1,
751 1, -1, 3, 1, -3, 2, -1, 1, 1, -2, -1, -1, -1, 1, 1, 1,
752 1, 1, -1, -1, -1, 2, -1, -2, 1, 2, -2, -1, 1, 1, 2, -1,
753 -1, 1, -2, -1, 1, 1, -1, 2, 1, 2, -1, 1, -2, -1, -2, -1,
754 -1, 1, 1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 4, -1, -1, -4,
755 1, 1, 1, 2, -1, -1, 1, -1, -1, 1, -1, -1, 1, -2, 1, -1,
756 1, 1, -1, -1, 1, 1, -1, -1, 3, 2, -3, -2, 2, 5, -2, 2,
757 2, -5, -2, -2, -2, 2, -3, 3, 2, 3, -3, 2, -2, -2, 3, -3,
758 6, 2, -2, 3, -6, 3, -3, -3, 3, 7, -4, 4, -3, 2, -7, 2,
759 2, -2, -4, 2, 8, -2, -2, -2, 4, 2, -2, 2, 3, 2, -2, -2,
760 2, 2, -2, -8, -2, 9, -2, 2, -3, -2, 2, -2, 2, 2, 2, 4,
761 -2, -4, 10, 2, 2, -2, -9, -2, 2, -2, 5, 4, -4, 4, -2, 2,
762 -5, -4, -3, 4, 2, -3, 3, -2, -5, 5, 3, 3, -2, -3, -10, -4}
768 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 0, 1, 1, 5, 5,
769 2, 2, 6, 6, 7, 7, 1, 8, 1, 8, 3, 3, 9, 9, 1, 2,
770 2, 1, 4, 10, 4, 10, 11, 11, 1, 5, 12, 12, 1, 5, 13, 13,
771 3, 3, 6, 6, 2, 2, 14, 14, 16, 16, 15, 7, 15, 8, 8, 7,
772 1, 1, 17, 17, 4, 4, 1, 1, 18, 18, 2, 2, 5, 5, 25, 3,
773 9, 3, 25, 9, 19, 24, 19, 24, 1, 21, 20, 1, 21, 22, 20, 22,
774 23, 23, 8, 6, 33, 6, 8, 33, 7, 7, 26, 26, 1, 32, 1, 32,
775 28, 4, 28, 10, 29, 27, 27, 10, 41, 4, 29, 2, 2, 41, 36, 31,
776 49, 31, 34, 30, 34, 36, 30, 35, 1, 49, 11, 5, 35, 11, 1, 3,
777 3, 5, 37, 37, 8, 40, 8, 40, 12, 12, 42, 42, 1, 38, 16, 57,
778 1, 6, 16, 39, 38, 6, 7, 7, 13, 13, 39, 43, 2, 43, 57, 2,
779 50, 9, 44, 9, 50, 4, 15, 48, 44, 4, 1, 15, 48, 14, 14, 1,
780 45, 45, 8, 3, 5, 8, 51, 47, 3, 46, 46, 47, 5, 51, 1, 17,
781 17, 58, 1, 58, 2, 52, 52, 2, 53, 7, 59, 6, 6, 56, 53, 55,
782 7, 55, 1, 54, 59, 56, 54, 10, 1, 10, 4, 60, 1, 60, 8, 4,
783 8, 64, 64, 61, 1, 63, 3, 63, 62, 61, 5, 11, 5, 3, 11, 62},
786 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 0, 3, -3, 1, -1,
787 2, -2, 1, -1, 1, -1, 4, 1, -4, -1, 2, -2, 1, -1, 5, 3,
788 -3, -5, 2, 1, -2, -1, 1, -1, 6, 2, 1, -1, -6, -2, 1, -1,
789 3, -3, 2, -2, 4, -4, 1, -1, 1, -1, 1, 2, -1, 2, -2, -2,
790 7, -7, 1, -1, 3, -3, 8, -8, 1, -1, 5, -5, 3, -3, 1, 4,
791 2, -4, -1, -2, 1, 1, -1, -1, 9, 1, 1, -9, -1, 1, -1, -1,
792 1, -1, 3, -3, 1, 3, -3, -1, 3, -3, 1, -1, 10, 1, -10, -1,
793 1, 4, -1, 2, 1, -1, 1, -2, 1, -4, -1, 6, -6, -1, 1, 1,
794 1, -1, 1, 1, -1, -1, -1, 1, 11, -1, -2, 4, -1, 2, -11, 5,
795 -5, -4, -1, 1, 4, 1, -4, -1, -2, 2, 1, -1, 12, 1, -2, 1,
796 -12, 4, 2, 1, -1, -4, 4, -4, 2, -2, -1, 1, 7, -1, -1, -7,
797 -1, -3, 1, 3, 1, 5, 2, 1, -1, -5, 13, -2, -1, 2, -2, -13,
798 1, -1, 5, 6, 5, -5, 1, 1, -6, 1, -1, -1, -5, -1, 14, 2,
799 -2, 1, -14, -1, 8, 1, -1, -8, 1, 5, 1, 5, -5, 1, -1, 1,
800 -5, -1, 15, 1, -1, -1, -1, 3, -15, -3, 6, 1, 16, -1, 6, -6,
801 -6, 1, -1, 1, -16, 1, 7, -1, 1, -1, -6, -3, 6, -7, 3, -1}
807 {0, 1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6, 6, 7,
808 7, 8, 8, 9, 9, 2, 2, 10, 10, 1, 1, 11, 11, 12, 12, 3,
809 3, 13, 13, 0, 14, 14, 16, 15, 16, 15, 4, 4, 17, 1, 17, 1,
810 5, 5, 18, 18, 2, 2, 6, 6, 8, 19, 7, 8, 7, 19, 20, 20,
811 21, 21, 22, 24, 22, 24, 23, 23, 1, 1, 25, 25, 3, 3, 26, 26,
812 9, 9, 27, 27, 28, 28, 33, 29, 4, 33, 29, 1, 4, 1, 32, 32,
813 2, 2, 31, 10, 30, 10, 30, 31, 34, 34, 5, 5, 36, 36, 35, 41,
814 35, 11, 41, 11, 37, 1, 8, 8, 37, 6, 1, 6, 40, 7, 7, 40,
815 12, 38, 12, 39, 39, 38, 49, 13, 49, 13, 3, 42, 3, 42, 16, 16,
816 43, 43, 14, 14, 1, 1, 44, 15, 44, 15, 2, 2, 57, 48, 50, 48,
817 57, 50, 4, 45, 45, 4, 46, 47, 47, 46, 1, 51, 1, 17, 17, 51,
818 8, 9, 9, 5, 58, 8, 58, 5, 52, 52, 55, 56, 53, 56, 55, 59,
819 59, 53, 54, 1, 6, 54, 7, 7, 6, 1, 2, 3, 2, 3, 64, 60,
820 60, 10, 10, 64, 61, 62, 61, 63, 1, 63, 62, 1, 18, 24, 18, 4,
821 25, 4, 8, 21, 21, 1, 24, 22, 25, 22, 8, 11, 19, 11, 23, 1,
822 20, 23, 19, 20, 5, 12, 5, 1, 16, 2, 12, 13, 2, 13, 1, 16},
825 { 0, 1, -1, 1, -1, 1, -1, 1, -1, 2, -2, 1, -1, 1, -1, 1,
826 -1, 1, -1, 1, -1, 2, -2, 1, -1, 3, -3, 1, -1, 1, -1, 2,
827 -2, 1, -1, 0, 1, -1, 1, 1, -1, -1, 2, -2, 1, 4, -1, -4,
828 2, -2, 1, -1, -3, 3, 2, -2, 2, 1, 2, -2, -2, -1, 1, -1,
829 1, -1, 1, 1, -1, -1, 1, -1, 5, -5, 1, -1, 3, -3, 1, -1,
830 2, -2, 1, -1, 1, -1, 1, 1, 3, -1, -1, 6, -3, -6, -1, 1,
831 4, -4, 1, 2, 1, -2, -1, -1, 1, -1, 3, -3, 1, -1, 1, 1,
832 -1, 2, -1, -2, 1, 7, -3, 3, -1, 3, -7, -3, 1, -3, 3, -1,
833 2, 1, -2, 1, -1, -1, 1, 2, -1, -2, -4, -1, 4, 1, 2, -2,
834 1, -1, -2, 2, 8, -8, -1, 2, 1, -2, -5, 5, 1, -1, -1, 1,
835 -1, 1, 4, -1, 1, -4, -1, -1, 1, 1, 9, 1, -9, 2, -2, -1,
836 -4, 3, -3, -4, -1, 4, 1, 4, 1, -1, 1, -1, 1, 1, -1, 1,
837 -1, -1, -1, 10, 4, 1, 4, -4, -4, -10, 6, 5, -6, -5, 1, -1,
838 1, 3, -3, -1, 1, -1, -1, -1, 11, 1, 1, -11, -2, -2, 2, 5,
839 -2, -5, -5, 2, -2, 12, 2, -2, 2, 2, 5, -3, -2, 3, -2, -12,
840 -2, 2, 2, 2, -5, 3, 5, 13, -3, 7, -3, -3, -7, 3, -13, 3}
846 {0, 1, 1, 1, 2, 2, 1, 3, 3, 1, 1, 1, 4, 4, 1, 5,
847 2, 1, 5, 2, 1, 1, 6, 6, 1, 1, 1, 1, 1, 7, 3, 1,
848 2, 3, 0, 1, 2, 7, 1, 1, 1, 8, 1, 1, 8, 1, 1, 1,
849 9, 1, 9, 1, 2, 1, 1, 2, 1, 1, 10, 4, 1, 10, 1, 4,
850 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 2, 1, 5, 1, 1, 1,
851 2, 5, 1, 11, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
852 2, 1, 6, 1, 6, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 12,
853 3, 1, 12, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1,
854 4, 1, 1, 1, 2, 1, 1, 4, 1, 1, 1, 1, 1, 1, 2, 1,
855 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 5,
856 1, 1, 1, 1, 1, 7, 1, 7, 1, 1, 2, 3, 1, 1, 1, 1,
857 5, 1, 1, 1, 1, 1, 1, 2, 13, 1, 1, 1, 1, 1, 1, 1,
858 1, 1, 1, 1, 1, 1, 1, 1, 13, 2, 1, 1, 4, 1, 1, 1,
859 3, 1, 6, 1, 1, 1, 14, 1, 1, 1, 1, 1, 14, 6, 1, 1,
860 1, 1, 15, 2, 4, 1, 2, 3, 15, 1, 1, 1, 8, 1, 1, 8,
861 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1},
864 { 0, 1, -1, 2, 1, -1, -2, 1, -1, 3, -3, 4, 1, -1, -4, 1,
865 2, 5, -1, -2, -5, 6, 1, -1, -6, 7, -7, 8, -8, 1, 2, 9,
866 3, -2, 0, -9, -3, -1, 10, -10, 11, 1, -11, 12, -1, -12, 13, -13,
867 1, 14, -1, -14, 4, 15, -15, -4, 16, -16, 1, 2, 17, -1, -17, -2,
868 18, -18, 19, -19, 20, 3, -20, 21, -21, -3, 5, 22, 2, -22, -23, 23,
869 -5, -2, 24, 1, -24, -1, 25, -25, 26, -26, -27, 27, 28, 29, -28, -29,
870 6, 30, 2, -31, -2, -30, 31, -6, -32, 32, 33, -33, 34, -35, -34, 1,
871 4, -36, -1, 35, 37, 36, 7, -37, 38, -4, -38, 39, 41, 40, -40, -39,
872 3, 42, -43, -41, -7, -42, 43, -3, 44, -44, 45, -45, 46, 47, 8, -47,
873 -48, -46, 50, -50, 48, 49, 51, -49, 52, -52, 5, -51, -8, -53, 53, 3,
874 -56, 56, 55, 54, -54, 2, 60, -2, -55, 58, 9, -5, 59, 57, -57, -63,
875 -3, -58, -60, -61, 61, -59, -62, -9, 1, 64, 62, 69, -64, 63, 65, -67,
876 -68, 66, -65, 68, -66, -69, 67, -70, -1, 10, 71, -71, 4, 73, 72, 70,
877 6, -76, -3, 74, -78, -74, 1, 78, 80, -72, -75, 76, -1, 3, -73, 79,
878 75, 77, 1, 11, -4, -79, -10, -6, -1, -77, -83, -80, 2, 81, -84, -2,
879 83, -81, 82, -82, 84, -87, -86, 85, -11, -85, 86, -89, 87, -88, 88, 89}
885 {1, 1, 0, 2, 1, 2, 1, 3, 3, 1, 1, 4, 4, 2, 2, 1,
886 1, 5, 5, 6, 1, 6, 1, 7, 7, 3, 3, 2, 8, 2, 8, 1,
887 1, 0, 9, 9, 1, 1, 10, 4, 10, 4, 11, 11, 2, 1, 2, 1,
888 12, 12, 3, 3, 1, 1, 13, 5, 5, 13, 14, 1, 1, 14, 2, 2,
889 6, 6, 15, 1, 1, 15, 16, 4, 7, 16, 4, 7, 1, 1, 3, 3,
890 8, 8, 2, 2, 1, 1, 17, 17, 1, 1, 18, 18, 5, 5, 2, 2,
891 1, 1, 9, 19, 9, 19, 20, 3, 3, 20, 1, 10, 21, 1, 10, 4,
892 4, 21, 22, 6, 6, 22, 1, 1, 23, 24, 2, 2, 23, 24, 11, 1,
893 1, 11, 7, 25, 7, 1, 1, 25, 8, 8, 3, 26, 3, 1, 12, 2,
894 2, 26, 1, 12, 5, 5, 27, 4, 1, 4, 1, 27, 28, 1, 28, 13,
895 1, 13, 2, 29, 2, 1, 32, 6, 1, 30, 14, 29, 14, 6, 3, 31,
896 3, 1, 30, 1, 32, 31, 33, 9, 33, 1, 1, 7, 9, 7, 2, 2,
897 1, 1, 4, 36, 34, 4, 5, 10, 10, 5, 34, 1, 1, 35, 8, 8,
898 36, 3, 35, 1, 15, 3, 2, 1, 16, 15, 16, 2, 37, 1, 37, 1,
899 1, 1, 6, 6, 38, 1, 38, 11, 1, 39, 39, 40, 11, 2, 41, 4,
900 40, 1, 2, 4, 1, 1, 1, 41, 3, 1, 3, 1, 5, 7, 5, 7},
903 { 1, -1, 0, 1, 2, -1, -2, 1, -1, 3, -3, 1, -1, 2, -2, 4,
904 -4, 1, -1, 1, 5, -1, -5, 1, -1, 2, -2, 3, 1, -3, -1, 6,
905 -6, 0, 1, -1, 7, -7, 1, 2, -1, -2, 1, -1, 4, 8, -4, -8,
906 1, -1, 3, -3, 9, -9, 1, 2, -2, -1, 1, 10, -10, -1, 5, -5,
907 2, -2, 1, 11, -11, -1, 1, 3, 2, -1, -3, -2, 12, -12, 4, -4,
908 2, -2, -6, 6, 13, -13, 1, -1, 14, -14, 1, -1, 3, -3, 7, -7,
909 15, -15, 2, 1, -2, -1, 1, 5, -5, -1, -16, 2, 1, 16, -2, 4,
910 -4, -1, 1, 3, -3, -1, 17, -17, 1, 1, -8, 8, -1, -1, 2, 18,
911 -18, -2, 3, 1, -3, 19, -19, -1, 3, -3, 6, 1, -6, 20, 2, 9,
912 -9, -1, -20, -2, 4, -4, 1, -5, 21, 5, -21, -1, 1, -22, -1, 2,
913 22, -2, 10, 1, -10, 23, 1, 4, -23, 1, 2, -1, -2, -4, -7, 1,
914 7, -24, -1, 24, -1, -1, 1, 3, -1, -25, 25, 4, -3, -4, 11, -11,
915 26, -26, 6, 1, 1, -6, -5, -3, 3, 5, -1, -27, 27, 1, 4, -4,
916 -1, -8, -1, 28, 2, 8, -12, -28, -2, -2, 2, 12, -1, 29, 1, -29,
917 30, -30, 5, -5, 1, -31, -1, 3, 31, -1, 1, 1, -3, -13, 1, -7,
918 -1, -32, 13, 7, 32, 33, -33, -1, -9, -34, 9, 34, -6, 5, 6, -5}
924 {1, 1, 0, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 0, 2, 2,
925 4, 1, 4, 1, 1, 1, 5, 5, 1, 1, 6, 6, 2, 2, 1, 1,
926 3, 3, 7, 7, 1, 1, 8, 8, 1, 1, 2, 2, 1, 9, 1, 9,
927 4, 4, 10, 1, 1, 10, 1, 1, 11, 11, 3, 3, 1, 2, 1, 2,
928 1, 1, 12, 12, 5, 5, 1, 1, 13, 1, 1, 13, 2, 2, 1, 1,
929 6, 6, 1, 1, 4, 14, 4, 14, 3, 1, 3, 1, 1, 1, 15, 7,
930 15, 2, 2, 7, 1, 1, 1, 8, 1, 8, 16, 16, 1, 1, 1, 1,
931 2, 1, 1, 2, 1, 1, 3, 5, 5, 3, 4, 1, 1, 4, 1, 1,
932 17, 17, 9, 1, 1, 9, 2, 2, 1, 1, 10, 10, 1, 6, 1, 1,
933 6, 18, 1, 1, 18, 1, 1, 1, 2, 2, 3, 1, 3, 1, 1, 1,
934 4, 1, 19, 1, 19, 7, 1, 1, 20, 1, 4, 20, 1, 7, 11, 2,
935 1, 11, 21, 2, 8, 5, 1, 8, 1, 5, 21, 1, 1, 1, 22, 1,
936 1, 22, 1, 1, 3, 3, 1, 23, 2, 12, 24, 1, 1, 2, 1, 1,
937 12, 23, 1, 1, 24, 1, 1, 1, 4, 1, 1, 1, 2, 1, 6, 6,
938 4, 2, 1, 1, 1, 1, 1, 1, 1, 14, 13, 3, 1, 25, 9, 25,
939 14, 1, 9, 3, 13, 1, 1, 1, 1, 1, 10, 1, 1, 2, 10, 2},
942 {-20, -1, 0, 2, -2, 1, -1, 3, -3, 1, -1, 4, -4, 0, 2, -2,
943 1, 5, -1, -5, 6, -6, 1, -1, 7, -7, 1, -1, 3, -3, 8, -8,
944 2, -2, 1, -1, 9, -9, 1, -1, 10, -10, 4, -4, 11, 1, -11, -1,
945 2, -2, 1, 12, -12, -1, 13, -13, 1, -1, 3, -3, 14, 5, -14, -5,
946 -15, 15, -1, 1, 2, -2, 16, -16, 1, 17, -17, -1, 6, -6, 18, -18,
947 2, -2, -19, 19, -3, 1, 3, -1, 4, 20, -4, 1, -21, 21, 1, 2,
948 -1, -7, 7, -2, 22, -22, 23, 2, -23, -2, 1, -1, -24, 24, -25, 25,
949 -8, -26, 26, 8, -27, 27, 5, 3, -3, -5, -4, 28, -28, 4, 29, -29,
950 1, -1, -2, -30, 30, 2, 9, -9, -31, 31, 2, -2, -32, 3, 32, -33,
951 -3, 1, 33, -34, -1, 34, -35, 35, -10, 10, -6, 36, 6, -36, 37, -37,
952 -5, 38, 1, -38, -1, 3, 39, -39, -1, 40, 5, 1, -40, -3, 2, -11,
953 -41, -2, 1, 11, -3, -4, 41, 3, 42, 4, -1, -43, -42, 43, 1, -44,
954 45, -1, 44, -45, -7, 7, -46, 1, -12, 2, 1, -47, 46, 12, 47, 48,
955 -2, -1, -48, 49, -1, -50, -49, 50, -6, -51, 51, 52, -13, 53, -4, 4,
956 6, 13, -53, -52, -54, 55, 54, -55, -56, -2, 2, -8, 56, 1, -3, -1,
957 2, 58, 3, 8, -2, 57, -58, -60, -59, -57, -3, 60, 59, -14, 3, 14}
963 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 5, 5, 1, 1, 6,
964 6, 2, 2, 7, 7, 8, 8, 1, 1, 3, 3, 9, 9, 10, 10, 1,
965 1, 2, 2, 4, 4, 11, 0, 11, 12, 12, 13, 13, 1, 1, 5, 5,
966 14, 14, 15, 16, 15, 16, 3, 3, 1, 6, 1, 6, 2, 2, 7, 7,
967 8, 8, 17, 17, 1, 1, 4, 4, 18, 18, 2, 2, 1, 19, 1, 20,
968 19, 20, 21, 21, 3, 3, 22, 22, 5, 5, 24, 1, 1, 23, 9, 23,
969 24, 9, 2, 2, 10, 1, 1, 10, 6, 6, 25, 4, 4, 25, 7, 7,
970 26, 8, 1, 8, 3, 1, 26, 3, 11, 11, 27, 27, 2, 28, 1, 2,
971 28, 1, 12, 12, 5, 5, 29, 13, 13, 29, 32, 1, 1, 33, 31, 30,
972 32, 4, 30, 33, 4, 31, 3, 14, 1, 1, 3, 34, 34, 2, 2, 14,
973 6, 6, 35, 36, 35, 36, 1, 15, 1, 16, 16, 15, 7, 9, 7, 9,
974 37, 8, 8, 37, 1, 1, 39, 2, 38, 39, 2, 40, 5, 38, 40, 5,
975 3, 3, 4, 4, 10, 10, 1, 1, 1, 1, 41, 2, 41, 2, 6, 6,
976 1, 1, 11, 42, 11, 43, 3, 42, 3, 17, 4, 43, 1, 17, 7, 1,
977 8, 44, 4, 7, 44, 5, 8, 2, 5, 1, 2, 48, 45, 1, 12, 45,
978 12, 48, 13, 13, 1, 9, 9, 46, 1, 46, 47, 47, 49, 18, 18, 49},
981 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 1, -1, 3, -3, 1,
982 -1, -2, 2, 1, -1, 1, -1, 4, -4, -2, 2, 1, -1, 1, -1, 5,
983 -5, -3, 3, 2, -2, 1, 0, -1, 1, -1, 1, -1, 6, -6, 2, -2,
984 1, -1, 1, 1, -1, -1, -3, 3, 7, 2, -7, -2, -4, 4, 2, -2,
985 2, -2, 1, -1, 8, -8, 3, -3, 1, -1, -5, 5, 9, 1, -9, 1,
986 -1, -1, 1, -1, -4, 4, 1, -1, 3, -3, 1, -10, 10, 1, 2, -1,
987 -1, -2, 6, -6, 2, 11, -11, -2, 3, -3, 1, -4, 4, -1, 3, -3,
988 1, 3, 12, -3, -5, -12, -1, 5, 2, -2, 1, -1, -7, 1, 13, 7,
989 -1, -13, 2, -2, 4, -4, 1, 2, -2, -1, 1, 14, -14, 1, 1, 1,
990 -1, -5, -1, -1, 5, -1, -6, 2, -15, 15, 6, 1, -1, -8, 8, -2,
991 -4, 4, 1, 1, -1, -1, 16, 2, -16, -2, 2, -2, 4, 3, -4, -3,
992 -1, -4, 4, 1, -17, 17, -1, -9, 1, 1, 9, 1, -5, -1, -1, 5,
993 -7, 7, 6, -6, 3, -3, 18, -18, 19, -19, 1, -10, -1, 10, -5, 5,
994 20, -20, -3, 1, 3, 1, 8, -1, -8, 2, 7, -1, -21, -2, 5, 21,
995 5, -1, -7, -5, 1, -6, -5, -11, 6, 22, 11, 1, 1, -22, -3, -1,
996 3, -1, 3, -3, -23, 4, -4, 1, 23, -1, 1, -1, 1, -2, 2, -1}
1002 {1, 1, 1, 1, 0, 2, 2, 1, 1, 3, 3, 0, 1, 1, 2, 2,
1003 4, 4, 1, 1, 5, 5, 1, 1, 2, 2, 3, 3, 6, 6, 1, 1,
1004 7, 7, 8, 1, 8, 2, 2, 1, 4, 4, 1, 3, 1, 3, 9, 9,
1005 2, 2, 1, 5, 1, 5, 10, 10, 1, 1, 11, 11, 3, 6, 3, 4,
1006 4, 6, 2, 2, 1, 12, 1, 12, 7, 13, 7, 13, 1, 1, 8, 8,
1007 2, 2, 14, 14, 16, 15, 16, 5, 5, 1, 3, 15, 1, 3, 4, 4,
1008 1, 1, 17, 17, 2, 2, 6, 6, 1, 18, 1, 18, 22, 21, 22, 21,
1009 25, 24, 25, 19, 9, 20, 9, 23, 19, 24, 20, 3, 23, 7, 3, 1,
1010 1, 7, 28, 26, 29, 5, 28, 26, 5, 8, 29, 4, 8, 27, 2, 2,
1011 4, 27, 1, 1, 10, 36, 10, 33, 33, 36, 30, 1, 32, 32, 1, 30,
1012 6, 31, 31, 35, 3, 6, 11, 11, 3, 2, 35, 2, 34, 1, 34, 1,
1013 37, 37, 12, 7, 12, 5, 41, 5, 4, 7, 1, 8, 13, 4, 1, 41,
1014 13, 38, 8, 38, 9, 1, 40, 40, 9, 1, 39, 2, 2, 49, 39, 42,
1015 3, 3, 14, 16, 49, 14, 16, 42, 43, 43, 6, 6, 15, 1, 1, 15,
1016 44, 44, 1, 1, 50, 48, 4, 5, 4, 7, 5, 2, 10, 10, 48, 7,
1017 50, 45, 2, 1, 45, 8, 8, 1, 46, 46, 3, 47, 47, 3, 1, 1},
1020 { 1, -1, 2, -2, 0, 1, -1, 3, -3, 1, -1, 0, 4, -4, 2, -2,
1021 1, -1, 5, -5, 1, -1, 6, -6, 3, -3, 2, -2, 1, -1, 7, -7,
1022 1, -1, 1, 8, -1, 4, -4, -8, 2, -2, 9, 3, -9, -3, 1, -1,
1023 5, -5, 10, 2, -10, -2, 1, -1, 11, -11, 1, -1, -4, 2, 4, 3,
1024 -3, -2, 6, -6, 12, 1, -12, -1, 2, 1, -2, -1, 13, -13, 2, -2,
1025 7, -7, 1, -1, 1, 1, -1, 3, -3, 14, 5, -1, -14, -5, 4, -4,
1026 15, -15, 1, -1, 8, -8, -3, 3, 16, 1, -16, -1, 1, 1, -1, -1,
1027 1, 1, -1, 1, 2, 1, -2, 1, -1, -1, -1, 6, -1, 3, -6, 17,
1028 -17, -3, 1, 1, 1, 4, -1, -1, -4, 3, -1, 5, -3, -1, -9, 9,
1029 -5, 1, 18, -18, 2, 1, -2, 1, -1, -1, 1, 19, -1, 1, -19, -1,
1030 4, 1, -1, 1, 7, -4, -2, 2, -7, 10, -1, -10, 1, 20, -1, -20,
1031 1, -1, 2, 4, -2, 5, 1, -5, 6, -4, 21, 4, 2, -6, -21, -1,
1032 -2, 1, -4, -1, -3, 22, -1, 1, 3, -22, -1, 11, -11, 1, 1, 1,
1033 8, -8, 2, 2, -1, -2, -2, -1, 1, -1, -5, 5, 2, 23, -23, -2,
1034 1, -1, 24, -24, -1, -1, 7, 6, -7, 5, -6, 12, -3, 3, 1, -5,
1035 1, 1, -12, 25, -1, -5, 5, -25, -1, 1, 9, 1, -1, -9, 26, -26}