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
24 * @file libavcodec/ivi_common.c
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 * Reverses "nbits" bits of the value "val" and returns 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 for (b = 0; b < planes[p].num_bands; b++) {
260 band = &planes[p].bands[b];
261 x_tiles = IVI_NUM_TILES(band->width, t_width);
262 y_tiles = IVI_NUM_TILES(band->height, t_height);
263 band->num_tiles = x_tiles * y_tiles;
265 av_freep(&band->tiles);
266 band->tiles = av_mallocz(band->num_tiles * sizeof(IVITile));
268 return AVERROR(ENOMEM);
272 /* use the first luma band as reference for motion vectors
274 ref_tile = planes[0].bands[0].tiles;
276 for (y = 0; y < band->height; y += t_height) {
277 for (x = 0; x < band->width; x += t_width) {
280 tile->width = FFMIN(band->width - x, t_width);
281 tile->height = FFMIN(band->height - y, t_height);
282 tile->is_empty = tile->data_size = 0;
283 /* calculate number of macroblocks */
284 tile->num_MBs = IVI_MBs_PER_TILE(tile->width, tile->height,
287 av_freep(&tile->mbs);
288 tile->mbs = av_malloc(tile->num_MBs * sizeof(IVIMbInfo));
290 return AVERROR(ENOMEM);
294 tile->ref_mbs = ref_tile->mbs;
308 int ff_ivi_dec_tile_data_size(GetBitContext *gb)
314 len = get_bits(gb, 8);
316 len = get_bits_long(gb, 24);
319 /* align the bitstream reader on the byte boundary */
325 int ff_ivi_decode_blocks(GetBitContext *gb, IVIBandDesc *band, IVITile *tile)
327 int mbn, blk, num_blocks, num_coeffs, blk_size, scan_pos, run, val,
328 pos, is_intra, mc_type, mv_x, mv_y, col_mask;
329 uint8_t col_flags[8];
330 int32_t prev_dc, trvec[64];
331 uint32_t cbp, sym, lo, hi, quant, buf_offs, q;
333 RVMapDesc *rvmap = band->rv_map;
334 void (*mc_with_delta_func)(int16_t *buf, const int16_t *ref_buf, uint32_t pitch, int mc_type);
335 void (*mc_no_delta_func) (int16_t *buf, const int16_t *ref_buf, uint32_t pitch, int mc_type);
336 const uint8_t *base_tab, *scale_tab;
338 prev_dc = 0; /* init intra prediction for the DC coefficient */
340 blk_size = band->blk_size;
341 col_mask = blk_size - 1; /* column mask for tracking non-zero coeffs */
342 num_blocks = (band->mb_size != blk_size) ? 4 : 1; /* number of blocks per mb */
343 num_coeffs = blk_size * blk_size;
345 mc_with_delta_func = ff_ivi_mc_8x8_delta;
346 mc_no_delta_func = ff_ivi_mc_8x8_no_delta;
348 mc_with_delta_func = ff_ivi_mc_4x4_delta;
349 mc_no_delta_func = ff_ivi_mc_4x4_no_delta;
352 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
353 is_intra = !mb->type;
355 buf_offs = mb->buf_offs;
357 quant = av_clip(band->glob_quant + mb->q_delta, 0, 23);
359 base_tab = is_intra ? band->intra_base : band->inter_base;
360 scale_tab = is_intra ? band->intra_scale : band->inter_scale;
365 if (!band->is_halfpel) {
366 mc_type = 0; /* we have only fullpel vectors */
368 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
370 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
374 for (blk = 0; blk < num_blocks; blk++) {
375 /* adjust block position in the buffer according to its number */
377 buf_offs += blk_size;
378 } else if (blk == 2) {
379 buf_offs -= blk_size;
380 buf_offs += blk_size * band->pitch;
383 if (cbp & 1) { /* block coded ? */
385 memset(trvec, 0, num_coeffs*sizeof(trvec[0])); /* zero transform vector */
386 memset(col_flags, 0, sizeof(col_flags)); /* zero column flags */
388 while (scan_pos <= num_coeffs) {
389 sym = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
390 if (sym == rvmap->eob_sym)
391 break; /* End of block */
393 if (sym == rvmap->esc_sym) { /* Escape - run/val explicitly coded using 3 vlc codes */
394 run = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1) + 1;
395 lo = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
396 hi = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
397 val = IVI_TOSIGNED((hi << 6) | lo); /* merge them and convert into signed val */
399 run = rvmap->runtab[sym];
400 val = rvmap->valtab[sym];
403 /* de-zigzag and dequantize */
405 if (scan_pos >= num_coeffs)
407 pos = band->scan[scan_pos];
409 if (IVI_DEBUG && !val)
410 av_log(NULL, AV_LOG_ERROR, "Val = 0 encountered!\n");
412 q = (base_tab[pos] * scale_tab[quant]) >> 8;
414 val = val * q + FFSIGN(val) * ((q >> 1) - (q & 1));
416 col_flags[pos & col_mask] |= val; /* track columns containing non-zero coeffs */
419 if (scan_pos >= num_coeffs && sym != rvmap->eob_sym)
420 return -1; /* corrupt block data */
422 /* undoing DC coeff prediction for intra-blocks */
423 if (is_intra && band->is_2d_trans) {
426 col_flags[0] |= !!prev_dc;
429 /* apply inverse transform */
430 band->inv_transform(trvec, band->buf + buf_offs,
431 band->pitch, col_flags);
433 /* apply motion compensation */
435 mc_with_delta_func(band->buf + buf_offs,
436 band->ref_buf + buf_offs + mv_y * band->pitch + mv_x,
437 band->pitch, mc_type);
439 /* block not coded */
440 /* for intra blocks apply the dc slant transform */
441 /* for inter - perform the motion compensation without delta */
442 if (is_intra && band->dc_transform) {
443 band->dc_transform(&prev_dc, band->buf + buf_offs,
444 band->pitch, blk_size);
446 mc_no_delta_func(band->buf + buf_offs,
447 band->ref_buf + buf_offs + mv_y * band->pitch + mv_x,
448 band->pitch, mc_type);
460 void ff_ivi_process_empty_tile(AVCodecContext *avctx, IVIBandDesc *band,
461 IVITile *tile, int32_t mv_scale)
463 int x, y, need_mc, mbn, blk, num_blocks, mv_x, mv_y, mc_type;
464 int offs, mb_offset, row_offset;
465 IVIMbInfo *mb, *ref_mb;
468 void (*mc_no_delta_func)(int16_t *buf, const int16_t *ref_buf, uint32_t pitch,
471 offs = tile->ypos * band->pitch + tile->xpos;
473 ref_mb = tile->ref_mbs;
474 row_offset = band->mb_size * band->pitch;
475 need_mc = 0; /* reset the mc tracking flag */
477 for (y = tile->ypos; y < (tile->ypos + tile->height); y += band->mb_size) {
480 for (x = tile->xpos; x < (tile->xpos + tile->width); x += band->mb_size) {
483 mb->buf_offs = mb_offset;
485 mb->type = 1; /* set the macroblocks type = INTER */
486 mb->cbp = 0; /* all blocks are empty */
488 if (!band->qdelta_present && !band->plane && !band->band_num) {
489 mb->q_delta = band->glob_quant;
494 if (band->inherit_qdelta && ref_mb)
495 mb->q_delta = ref_mb->q_delta;
497 if (band->inherit_mv) {
498 /* motion vector inheritance */
500 mb->mv_x = ivi_scale_mv(ref_mb->mv_x, mv_scale);
501 mb->mv_y = ivi_scale_mv(ref_mb->mv_y, mv_scale);
503 mb->mv_x = ref_mb->mv_x;
504 mb->mv_y = ref_mb->mv_y;
506 need_mc |= mb->mv_x || mb->mv_y; /* tracking non-zero motion vectors */
512 mb_offset += band->mb_size;
517 if (band->inherit_mv && need_mc) { /* apply motion compensation if there is at least one non-zero motion vector */
518 num_blocks = (band->mb_size != band->blk_size) ? 4 : 1; /* number of blocks per mb */
519 mc_no_delta_func = (band->blk_size == 8) ? ff_ivi_mc_8x8_no_delta
520 : ff_ivi_mc_4x4_no_delta;
522 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
525 if (!band->is_halfpel) {
526 mc_type = 0; /* we have only fullpel vectors */
528 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
530 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
533 for (blk = 0; blk < num_blocks; blk++) {
534 /* adjust block position in the buffer according with its number */
535 offs = mb->buf_offs + band->blk_size * ((blk & 1) + !!(blk & 2) * band->pitch);
536 mc_no_delta_func(band->buf + offs,
537 band->ref_buf + offs + mv_y * band->pitch + mv_x,
538 band->pitch, mc_type);
542 /* copy data from the reference tile into the current one */
543 src = band->ref_buf + tile->ypos * band->pitch + tile->xpos;
544 dst = band->buf + tile->ypos * band->pitch + tile->xpos;
545 for (y = 0; y < tile->height; y++) {
546 memcpy(dst, src, tile->width*sizeof(band->buf[0]));
555 uint16_t ivi_calc_band_checksum (IVIBandDesc *band)
558 int16_t *src, checksum;
563 for (y = 0; y < band->height; src += band->pitch, y++)
564 for (x = 0; x < band->width; x++)
570 int ivi_check_band (IVIBandDesc *band, const uint8_t *ref, int pitch)
579 for (y = 0; y < band->height; src += band->pitch, y++) {
580 for (x = 0; x < band->width; x++) {
581 t1 = av_clip(src[x] + 128, 0, 255);
584 av_log(NULL, AV_LOG_ERROR, "Data mismatch: row %d, column %d\n",
585 y / band->blk_size, x / band->blk_size);
596 void ff_ivi_output_plane(IVIPlaneDesc *plane, uint8_t *dst, int dst_pitch)
599 const int16_t *src = plane->bands[0].buf;
600 uint32_t pitch = plane->bands[0].pitch;
602 for (y = 0; y < plane->height; y++) {
603 for (x = 0; x < plane->width; x++)
604 dst[x] = av_clip_uint8(src[x] + 128);
612 * These are 2x8 predefined Huffman codebooks for coding macroblock/block
613 * signals. They are specified using "huffman descriptors" in order to
614 * avoid huge static tables. The decoding tables will be generated at
615 * startup from these descriptors.
617 const IVIHuffDesc ff_ivi_mb_huff_desc[8] = {
618 {8, {0, 4, 5, 4, 4, 4, 6, 6}},
619 {12, {0, 2, 2, 3, 3, 3, 3, 5, 3, 2, 2, 2}},
620 {12, {0, 2, 3, 4, 3, 3, 3, 3, 4, 3, 2, 2}},
621 {12, {0, 3, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2}},
622 {13, {0, 4, 4, 3, 3, 3, 3, 2, 3, 3, 2, 1, 1}},
623 {9, {0, 4, 4, 4, 4, 3, 3, 3, 2}},
624 {10, {0, 4, 4, 4, 4, 3, 3, 2, 2, 2}},
625 {12, {0, 4, 4, 4, 3, 3, 2, 3, 2, 2, 2, 2}}
628 const IVIHuffDesc ff_ivi_blk_huff_desc[8] = {
629 {10, {1, 2, 3, 4, 4, 7, 5, 5, 4, 1}},
630 {11, {2, 3, 4, 4, 4, 7, 5, 4, 3, 3, 2}},
631 {12, {2, 4, 5, 5, 5, 5, 6, 4, 4, 3, 1, 1}},
632 {13, {3, 3, 4, 4, 5, 6, 6, 4, 4, 3, 2, 1, 1}},
633 {11, {3, 4, 4, 5, 5, 5, 6, 5, 4, 2, 2}},
634 {13, {3, 4, 5, 5, 5, 5, 6, 4, 3, 3, 2, 1, 1}},
635 {13, {3, 4, 5, 5, 5, 6, 5, 4, 3, 3, 2, 1, 1}},
636 {9, {3, 4, 4, 5, 5, 5, 6, 5, 5}}
641 * Run-value (RLE) tables.
643 const RVMapDesc ff_ivi_rvmap_tabs[9] = {
648 {1, 1, 0, 1, 1, 0, 1, 1, 2, 2, 1, 1, 1, 1, 3, 3,
649 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 1, 1, 2, 2, 5, 5,
650 1, 1, 3, 3, 1, 1, 6, 6, 1, 2, 1, 2, 7, 7, 1, 1,
651 8, 8, 1, 1, 4, 2, 1, 4, 2, 1, 3, 3, 1, 1, 1, 9,
652 9, 1, 2, 1, 2, 1, 5, 5, 1, 1, 10, 10, 1, 1, 3, 3,
653 2, 2, 1, 1, 11, 11, 6, 4, 4, 1, 6, 1, 2, 1, 2, 12,
654 8, 1, 12, 7, 8, 7, 1, 16, 1, 16, 1, 3, 3, 13, 1, 13,
655 2, 2, 1, 15, 1, 5, 14, 15, 1, 5, 14, 1, 17, 8, 17, 8,
656 1, 4, 4, 2, 2, 1, 25, 25, 24, 24, 1, 3, 1, 3, 1, 8,
657 6, 7, 6, 1, 18, 8, 18, 1, 7, 23, 2, 2, 23, 1, 1, 21,
658 22, 9, 9, 22, 19, 1, 21, 5, 19, 5, 1, 33, 20, 33, 20, 8,
659 4, 4, 1, 32, 2, 2, 8, 3, 32, 26, 3, 1, 7, 7, 26, 6,
660 1, 6, 1, 1, 16, 1, 10, 1, 10, 2, 16, 29, 28, 2, 29, 28,
661 1, 27, 5, 8, 5, 27, 1, 8, 3, 7, 3, 31, 41, 31, 1, 41,
662 6, 1, 6, 7, 4, 4, 1, 1, 2, 1, 2, 11, 34, 30, 11, 1,
663 30, 15, 15, 34, 36, 40, 36, 40, 35, 35, 37, 37, 39, 39, 38, 38},
666 { 1, -1, 0, 2, -2, 0, 3, -3, 1, -1, 4, -4, 5, -5, 1, -1,
667 6, -6, 2, -2, 7, -7, 1, -1, 8, -8, 9, -9, 3, -3, 1, -1,
668 10, -10, 2, -2, 11, -11, 1, -1, 12, 4, -12, -4, 1, -1, 13, -13,
669 1, -1, 14, -14, 2, 5, 15, -2, -5, -15, -3, 3, 16, -16, 17, 1,
670 -1, -17, 6, 18, -6, -18, 2, -2, 19, -19, 1, -1, 20, -20, 4, -4,
671 7, -7, 21, -21, 1, -1, 2, 3, -3, 22, -2, -22, 8, 23, -8, 1,
672 2, -23, -1, 2, -2, -2, 24, 1, -24, -1, 25, 5, -5, 1, -25, -1,
673 9, -9, 26, 1, -26, 3, 1, -1, 27, -3, -1, -27, 1, 3, -1, -3,
674 28, -4, 4, 10, -10, -28, 1, -1, 1, -1, 29, 6, -29, -6, 30, -4,
675 3, 3, -3, -30, 1, 4, -1, 31, -3, 1, 11, -11, -1, -31, 32, -1,
676 -1, 2, -2, 1, 1, -32, 1, 4, -1, -4, 33, -1, 1, 1, -1, 5,
677 5, -5, -33, -1, -12, 12, -5, -7, 1, 1, 7, 34, 4, -4, -1, 4,
678 -34, -4, 35, 36, -2, -35, -2, -36, 2, 13, 2, -1, 1, -13, 1, -1,
679 37, 1, -5, 6, 5, -1, 38, -6, -8, 5, 8, -1, 1, 1, -37, -1,
680 5, 39, -5, -5, 6, -6, -38, -39, -14, 40, 14, 2, 1, 1, -2, -40,
681 -1, -2, 2, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1}
687 {0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 8, 6, 8, 7,
688 7, 9, 9, 10, 10, 11, 11, 1, 12, 1, 12, 13, 13, 16, 14, 16,
689 14, 15, 15, 17, 17, 18, 0, 18, 19, 20, 21, 19, 22, 21, 20, 22,
690 25, 24, 2, 25, 24, 23, 23, 2, 26, 28, 26, 28, 29, 27, 29, 27,
691 33, 33, 1, 32, 1, 3, 32, 30, 36, 3, 36, 30, 31, 31, 35, 34,
692 37, 41, 34, 35, 37, 4, 41, 4, 49, 8, 8, 49, 40, 38, 5, 38,
693 40, 39, 5, 39, 42, 43, 42, 7, 57, 6, 43, 44, 6, 50, 7, 44,
694 57, 48, 50, 48, 45, 45, 46, 47, 51, 46, 47, 58, 1, 51, 58, 1,
695 52, 59, 53, 9, 52, 55, 55, 59, 53, 56, 54, 56, 54, 9, 64, 64,
696 60, 63, 60, 63, 61, 62, 61, 62, 2, 10, 2, 10, 11, 1, 11, 13,
697 12, 1, 12, 13, 16, 16, 8, 8, 14, 3, 3, 15, 14, 15, 4, 4,
698 1, 17, 17, 5, 1, 7, 7, 5, 6, 1, 2, 2, 6, 22, 1, 25,
699 21, 22, 8, 24, 1, 21, 25, 24, 8, 18, 18, 23, 9, 20, 23, 33,
700 29, 33, 20, 1, 19, 1, 29, 36, 9, 36, 19, 41, 28, 57, 32, 3,
701 28, 3, 1, 27, 49, 49, 1, 32, 26, 26, 2, 4, 4, 7, 57, 41,
702 2, 7, 10, 5, 37, 16, 10, 27, 8, 8, 13, 16, 37, 13, 1, 5},
705 {0, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1,
706 -1, 1, -1, 1, -1, 1, -1, 2, 1, -2, -1, 1, -1, 1, 1, -1,
707 -1, 1, -1, 1, -1, 1, 0, -1, 1, 1, 1, -1, 1, -1, -1, -1,
708 1, 1, 2, -1, -1, 1, -1, -2, 1, 1, -1, -1, 1, 1, -1, -1,
709 1, -1, 3, 1, -3, 2, -1, 1, 1, -2, -1, -1, -1, 1, 1, 1,
710 1, 1, -1, -1, -1, 2, -1, -2, 1, 2, -2, -1, 1, 1, 2, -1,
711 -1, 1, -2, -1, 1, 1, -1, 2, 1, 2, -1, 1, -2, -1, -2, -1,
712 -1, 1, 1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 4, -1, -1, -4,
713 1, 1, 1, 2, -1, -1, 1, -1, -1, 1, -1, -1, 1, -2, 1, -1,
714 1, 1, -1, -1, 1, 1, -1, -1, 3, 2, -3, -2, 2, 5, -2, 2,
715 2, -5, -2, -2, -2, 2, -3, 3, 2, 3, -3, 2, -2, -2, 3, -3,
716 6, 2, -2, 3, -6, 3, -3, -3, 3, 7, -4, 4, -3, 2, -7, 2,
717 2, -2, -4, 2, 8, -2, -2, -2, 4, 2, -2, 2, 3, 2, -2, -2,
718 2, 2, -2, -8, -2, 9, -2, 2, -3, -2, 2, -2, 2, 2, 2, 4,
719 -2, -4, 10, 2, 2, -2, -9, -2, 2, -2, 5, 4, -4, 4, -2, 2,
720 -5, -4, -3, 4, 2, -3, 3, -2, -5, 5, 3, 3, -2, -3, -10, -4}
726 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 0, 1, 1, 5, 5,
727 2, 2, 6, 6, 7, 7, 1, 8, 1, 8, 3, 3, 9, 9, 1, 2,
728 2, 1, 4, 10, 4, 10, 11, 11, 1, 5, 12, 12, 1, 5, 13, 13,
729 3, 3, 6, 6, 2, 2, 14, 14, 16, 16, 15, 7, 15, 8, 8, 7,
730 1, 1, 17, 17, 4, 4, 1, 1, 18, 18, 2, 2, 5, 5, 25, 3,
731 9, 3, 25, 9, 19, 24, 19, 24, 1, 21, 20, 1, 21, 22, 20, 22,
732 23, 23, 8, 6, 33, 6, 8, 33, 7, 7, 26, 26, 1, 32, 1, 32,
733 28, 4, 28, 10, 29, 27, 27, 10, 41, 4, 29, 2, 2, 41, 36, 31,
734 49, 31, 34, 30, 34, 36, 30, 35, 1, 49, 11, 5, 35, 11, 1, 3,
735 3, 5, 37, 37, 8, 40, 8, 40, 12, 12, 42, 42, 1, 38, 16, 57,
736 1, 6, 16, 39, 38, 6, 7, 7, 13, 13, 39, 43, 2, 43, 57, 2,
737 50, 9, 44, 9, 50, 4, 15, 48, 44, 4, 1, 15, 48, 14, 14, 1,
738 45, 45, 8, 3, 5, 8, 51, 47, 3, 46, 46, 47, 5, 51, 1, 17,
739 17, 58, 1, 58, 2, 52, 52, 2, 53, 7, 59, 6, 6, 56, 53, 55,
740 7, 55, 1, 54, 59, 56, 54, 10, 1, 10, 4, 60, 1, 60, 8, 4,
741 8, 64, 64, 61, 1, 63, 3, 63, 62, 61, 5, 11, 5, 3, 11, 62},
744 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 0, 3, -3, 1, -1,
745 2, -2, 1, -1, 1, -1, 4, 1, -4, -1, 2, -2, 1, -1, 5, 3,
746 -3, -5, 2, 1, -2, -1, 1, -1, 6, 2, 1, -1, -6, -2, 1, -1,
747 3, -3, 2, -2, 4, -4, 1, -1, 1, -1, 1, 2, -1, 2, -2, -2,
748 7, -7, 1, -1, 3, -3, 8, -8, 1, -1, 5, -5, 3, -3, 1, 4,
749 2, -4, -1, -2, 1, 1, -1, -1, 9, 1, 1, -9, -1, 1, -1, -1,
750 1, -1, 3, -3, 1, 3, -3, -1, 3, -3, 1, -1, 10, 1, -10, -1,
751 1, 4, -1, 2, 1, -1, 1, -2, 1, -4, -1, 6, -6, -1, 1, 1,
752 1, -1, 1, 1, -1, -1, -1, 1, 11, -1, -2, 4, -1, 2, -11, 5,
753 -5, -4, -1, 1, 4, 1, -4, -1, -2, 2, 1, -1, 12, 1, -2, 1,
754 -12, 4, 2, 1, -1, -4, 4, -4, 2, -2, -1, 1, 7, -1, -1, -7,
755 -1, -3, 1, 3, 1, 5, 2, 1, -1, -5, 13, -2, -1, 2, -2, -13,
756 1, -1, 5, 6, 5, -5, 1, 1, -6, 1, -1, -1, -5, -1, 14, 2,
757 -2, 1, -14, -1, 8, 1, -1, -8, 1, 5, 1, 5, -5, 1, -1, 1,
758 -5, -1, 15, 1, -1, -1, -1, 3, -15, -3, 6, 1, 16, -1, 6, -6,
759 -6, 1, -1, 1, -16, 1, 7, -1, 1, -1, -6, -3, 6, -7, 3, -1}
765 {0, 1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6, 6, 7,
766 7, 8, 8, 9, 9, 2, 2, 10, 10, 1, 1, 11, 11, 12, 12, 3,
767 3, 13, 13, 0, 14, 14, 16, 15, 16, 15, 4, 4, 17, 1, 17, 1,
768 5, 5, 18, 18, 2, 2, 6, 6, 8, 19, 7, 8, 7, 19, 20, 20,
769 21, 21, 22, 24, 22, 24, 23, 23, 1, 1, 25, 25, 3, 3, 26, 26,
770 9, 9, 27, 27, 28, 28, 33, 29, 4, 33, 29, 1, 4, 1, 32, 32,
771 2, 2, 31, 10, 30, 10, 30, 31, 34, 34, 5, 5, 36, 36, 35, 41,
772 35, 11, 41, 11, 37, 1, 8, 8, 37, 6, 1, 6, 40, 7, 7, 40,
773 12, 38, 12, 39, 39, 38, 49, 13, 49, 13, 3, 42, 3, 42, 16, 16,
774 43, 43, 14, 14, 1, 1, 44, 15, 44, 15, 2, 2, 57, 48, 50, 48,
775 57, 50, 4, 45, 45, 4, 46, 47, 47, 46, 1, 51, 1, 17, 17, 51,
776 8, 9, 9, 5, 58, 8, 58, 5, 52, 52, 55, 56, 53, 56, 55, 59,
777 59, 53, 54, 1, 6, 54, 7, 7, 6, 1, 2, 3, 2, 3, 64, 60,
778 60, 10, 10, 64, 61, 62, 61, 63, 1, 63, 62, 1, 18, 24, 18, 4,
779 25, 4, 8, 21, 21, 1, 24, 22, 25, 22, 8, 11, 19, 11, 23, 1,
780 20, 23, 19, 20, 5, 12, 5, 1, 16, 2, 12, 13, 2, 13, 1, 16},
783 { 0, 1, -1, 1, -1, 1, -1, 1, -1, 2, -2, 1, -1, 1, -1, 1,
784 -1, 1, -1, 1, -1, 2, -2, 1, -1, 3, -3, 1, -1, 1, -1, 2,
785 -2, 1, -1, 0, 1, -1, 1, 1, -1, -1, 2, -2, 1, 4, -1, -4,
786 2, -2, 1, -1, -3, 3, 2, -2, 2, 1, 2, -2, -2, -1, 1, -1,
787 1, -1, 1, 1, -1, -1, 1, -1, 5, -5, 1, -1, 3, -3, 1, -1,
788 2, -2, 1, -1, 1, -1, 1, 1, 3, -1, -1, 6, -3, -6, -1, 1,
789 4, -4, 1, 2, 1, -2, -1, -1, 1, -1, 3, -3, 1, -1, 1, 1,
790 -1, 2, -1, -2, 1, 7, -3, 3, -1, 3, -7, -3, 1, -3, 3, -1,
791 2, 1, -2, 1, -1, -1, 1, 2, -1, -2, -4, -1, 4, 1, 2, -2,
792 1, -1, -2, 2, 8, -8, -1, 2, 1, -2, -5, 5, 1, -1, -1, 1,
793 -1, 1, 4, -1, 1, -4, -1, -1, 1, 1, 9, 1, -9, 2, -2, -1,
794 -4, 3, -3, -4, -1, 4, 1, 4, 1, -1, 1, -1, 1, 1, -1, 1,
795 -1, -1, -1, 10, 4, 1, 4, -4, -4, -10, 6, 5, -6, -5, 1, -1,
796 1, 3, -3, -1, 1, -1, -1, -1, 11, 1, 1, -11, -2, -2, 2, 5,
797 -2, -5, -5, 2, -2, 12, 2, -2, 2, 2, 5, -3, -2, 3, -2, -12,
798 -2, 2, 2, 2, -5, 3, 5, 13, -3, 7, -3, -3, -7, 3, -13, 3}
804 {0, 1, 1, 1, 2, 2, 1, 3, 3, 1, 1, 1, 4, 4, 1, 5,
805 2, 1, 5, 2, 1, 1, 6, 6, 1, 1, 1, 1, 1, 7, 3, 1,
806 2, 3, 0, 1, 2, 7, 1, 1, 1, 8, 1, 1, 8, 1, 1, 1,
807 9, 1, 9, 1, 2, 1, 1, 2, 1, 1, 10, 4, 1, 10, 1, 4,
808 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 2, 1, 5, 1, 1, 1,
809 2, 5, 1, 11, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
810 2, 1, 6, 1, 6, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 12,
811 3, 1, 12, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1,
812 4, 1, 1, 1, 2, 1, 1, 4, 1, 1, 1, 1, 1, 1, 2, 1,
813 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 5,
814 1, 1, 1, 1, 1, 7, 1, 7, 1, 1, 2, 3, 1, 1, 1, 1,
815 5, 1, 1, 1, 1, 1, 1, 2, 13, 1, 1, 1, 1, 1, 1, 1,
816 1, 1, 1, 1, 1, 1, 1, 1, 13, 2, 1, 1, 4, 1, 1, 1,
817 3, 1, 6, 1, 1, 1, 14, 1, 1, 1, 1, 1, 14, 6, 1, 1,
818 1, 1, 15, 2, 4, 1, 2, 3, 15, 1, 1, 1, 8, 1, 1, 8,
819 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1},
822 { 0, 1, -1, 2, 1, -1, -2, 1, -1, 3, -3, 4, 1, -1, -4, 1,
823 2, 5, -1, -2, -5, 6, 1, -1, -6, 7, -7, 8, -8, 1, 2, 9,
824 3, -2, 0, -9, -3, -1, 10, -10, 11, 1, -11, 12, -1, -12, 13, -13,
825 1, 14, -1, -14, 4, 15, -15, -4, 16, -16, 1, 2, 17, -1, -17, -2,
826 18, -18, 19, -19, 20, 3, -20, 21, -21, -3, 5, 22, 2, -22, -23, 23,
827 -5, -2, 24, 1, -24, -1, 25, -25, 26, -26, -27, 27, 28, 29, -28, -29,
828 6, 30, 2, -31, -2, -30, 31, -6, -32, 32, 33, -33, 34, -35, -34, 1,
829 4, -36, -1, 35, 37, 36, 7, -37, 38, -4, -38, 39, 41, 40, -40, -39,
830 3, 42, -43, -41, -7, -42, 43, -3, 44, -44, 45, -45, 46, 47, 8, -47,
831 -48, -46, 50, -50, 48, 49, 51, -49, 52, -52, 5, -51, -8, -53, 53, 3,
832 -56, 56, 55, 54, -54, 2, 60, -2, -55, 58, 9, -5, 59, 57, -57, -63,
833 -3, -58, -60, -61, 61, -59, -62, -9, 1, 64, 62, 69, -64, 63, 65, -67,
834 -68, 66, -65, 68, -66, -69, 67, -70, -1, 10, 71, -71, 4, 73, 72, 70,
835 6, -76, -3, 74, -78, -74, 1, 78, 80, -72, -75, 76, -1, 3, -73, 79,
836 75, 77, 1, 11, -4, -79, -10, -6, -1, -77, -83, -80, 2, 81, -84, -2,
837 83, -81, 82, -82, 84, -87, -86, 85, -11, -85, 86, -89, 87, -88, 88, 89}
843 {1, 1, 0, 2, 1, 2, 1, 3, 3, 1, 1, 4, 4, 2, 2, 1,
844 1, 5, 5, 6, 1, 6, 1, 7, 7, 3, 3, 2, 8, 2, 8, 1,
845 1, 0, 9, 9, 1, 1, 10, 4, 10, 4, 11, 11, 2, 1, 2, 1,
846 12, 12, 3, 3, 1, 1, 13, 5, 5, 13, 14, 1, 1, 14, 2, 2,
847 6, 6, 15, 1, 1, 15, 16, 4, 7, 16, 4, 7, 1, 1, 3, 3,
848 8, 8, 2, 2, 1, 1, 17, 17, 1, 1, 18, 18, 5, 5, 2, 2,
849 1, 1, 9, 19, 9, 19, 20, 3, 3, 20, 1, 10, 21, 1, 10, 4,
850 4, 21, 22, 6, 6, 22, 1, 1, 23, 24, 2, 2, 23, 24, 11, 1,
851 1, 11, 7, 25, 7, 1, 1, 25, 8, 8, 3, 26, 3, 1, 12, 2,
852 2, 26, 1, 12, 5, 5, 27, 4, 1, 4, 1, 27, 28, 1, 28, 13,
853 1, 13, 2, 29, 2, 1, 32, 6, 1, 30, 14, 29, 14, 6, 3, 31,
854 3, 1, 30, 1, 32, 31, 33, 9, 33, 1, 1, 7, 9, 7, 2, 2,
855 1, 1, 4, 36, 34, 4, 5, 10, 10, 5, 34, 1, 1, 35, 8, 8,
856 36, 3, 35, 1, 15, 3, 2, 1, 16, 15, 16, 2, 37, 1, 37, 1,
857 1, 1, 6, 6, 38, 1, 38, 11, 1, 39, 39, 40, 11, 2, 41, 4,
858 40, 1, 2, 4, 1, 1, 1, 41, 3, 1, 3, 1, 5, 7, 5, 7},
861 { 1, -1, 0, 1, 2, -1, -2, 1, -1, 3, -3, 1, -1, 2, -2, 4,
862 -4, 1, -1, 1, 5, -1, -5, 1, -1, 2, -2, 3, 1, -3, -1, 6,
863 -6, 0, 1, -1, 7, -7, 1, 2, -1, -2, 1, -1, 4, 8, -4, -8,
864 1, -1, 3, -3, 9, -9, 1, 2, -2, -1, 1, 10, -10, -1, 5, -5,
865 2, -2, 1, 11, -11, -1, 1, 3, 2, -1, -3, -2, 12, -12, 4, -4,
866 2, -2, -6, 6, 13, -13, 1, -1, 14, -14, 1, -1, 3, -3, 7, -7,
867 15, -15, 2, 1, -2, -1, 1, 5, -5, -1, -16, 2, 1, 16, -2, 4,
868 -4, -1, 1, 3, -3, -1, 17, -17, 1, 1, -8, 8, -1, -1, 2, 18,
869 -18, -2, 3, 1, -3, 19, -19, -1, 3, -3, 6, 1, -6, 20, 2, 9,
870 -9, -1, -20, -2, 4, -4, 1, -5, 21, 5, -21, -1, 1, -22, -1, 2,
871 22, -2, 10, 1, -10, 23, 1, 4, -23, 1, 2, -1, -2, -4, -7, 1,
872 7, -24, -1, 24, -1, -1, 1, 3, -1, -25, 25, 4, -3, -4, 11, -11,
873 26, -26, 6, 1, 1, -6, -5, -3, 3, 5, -1, -27, 27, 1, 4, -4,
874 -1, -8, -1, 28, 2, 8, -12, -28, -2, -2, 2, 12, -1, 29, 1, -29,
875 30, -30, 5, -5, 1, -31, -1, 3, 31, -1, 1, 1, -3, -13, 1, -7,
876 -1, -32, 13, 7, 32, 33, -33, -1, -9, -34, 9, 34, -6, 5, 6, -5}
882 {1, 1, 0, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 0, 2, 2,
883 4, 1, 4, 1, 1, 1, 5, 5, 1, 1, 6, 6, 2, 2, 1, 1,
884 3, 3, 7, 7, 1, 1, 8, 8, 1, 1, 2, 2, 1, 9, 1, 9,
885 4, 4, 10, 1, 1, 10, 1, 1, 11, 11, 3, 3, 1, 2, 1, 2,
886 1, 1, 12, 12, 5, 5, 1, 1, 13, 1, 1, 13, 2, 2, 1, 1,
887 6, 6, 1, 1, 4, 14, 4, 14, 3, 1, 3, 1, 1, 1, 15, 7,
888 15, 2, 2, 7, 1, 1, 1, 8, 1, 8, 16, 16, 1, 1, 1, 1,
889 2, 1, 1, 2, 1, 1, 3, 5, 5, 3, 4, 1, 1, 4, 1, 1,
890 17, 17, 9, 1, 1, 9, 2, 2, 1, 1, 10, 10, 1, 6, 1, 1,
891 6, 18, 1, 1, 18, 1, 1, 1, 2, 2, 3, 1, 3, 1, 1, 1,
892 4, 1, 19, 1, 19, 7, 1, 1, 20, 1, 4, 20, 1, 7, 11, 2,
893 1, 11, 21, 2, 8, 5, 1, 8, 1, 5, 21, 1, 1, 1, 22, 1,
894 1, 22, 1, 1, 3, 3, 1, 23, 2, 12, 24, 1, 1, 2, 1, 1,
895 12, 23, 1, 1, 24, 1, 1, 1, 4, 1, 1, 1, 2, 1, 6, 6,
896 4, 2, 1, 1, 1, 1, 1, 1, 1, 14, 13, 3, 1, 25, 9, 25,
897 14, 1, 9, 3, 13, 1, 1, 1, 1, 1, 10, 1, 1, 2, 10, 2},
900 {-20, -1, 0, 2, -2, 1, -1, 3, -3, 1, -1, 4, -4, 0, 2, -2,
901 1, 5, -1, -5, 6, -6, 1, -1, 7, -7, 1, -1, 3, -3, 8, -8,
902 2, -2, 1, -1, 9, -9, 1, -1, 10, -10, 4, -4, 11, 1, -11, -1,
903 2, -2, 1, 12, -12, -1, 13, -13, 1, -1, 3, -3, 14, 5, -14, -5,
904 -15, 15, -1, 1, 2, -2, 16, -16, 1, 17, -17, -1, 6, -6, 18, -18,
905 2, -2, -19, 19, -3, 1, 3, -1, 4, 20, -4, 1, -21, 21, 1, 2,
906 -1, -7, 7, -2, 22, -22, 23, 2, -23, -2, 1, -1, -24, 24, -25, 25,
907 -8, -26, 26, 8, -27, 27, 5, 3, -3, -5, -4, 28, -28, 4, 29, -29,
908 1, -1, -2, -30, 30, 2, 9, -9, -31, 31, 2, -2, -32, 3, 32, -33,
909 -3, 1, 33, -34, -1, 34, -35, 35, -10, 10, -6, 36, 6, -36, 37, -37,
910 -5, 38, 1, -38, -1, 3, 39, -39, -1, 40, 5, 1, -40, -3, 2, -11,
911 -41, -2, 1, 11, -3, -4, 41, 3, 42, 4, -1, -43, -42, 43, 1, -44,
912 45, -1, 44, -45, -7, 7, -46, 1, -12, 2, 1, -47, 46, 12, 47, 48,
913 -2, -1, -48, 49, -1, -50, -49, 50, -6, -51, 51, 52, -13, 53, -4, 4,
914 6, 13, -53, -52, -54, 55, 54, -55, -56, -2, 2, -8, 56, 1, -3, -1,
915 2, 58, 3, 8, -2, 57, -58, -60, -59, -57, -3, 60, 59, -14, 3, 14}
921 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 5, 5, 1, 1, 6,
922 6, 2, 2, 7, 7, 8, 8, 1, 1, 3, 3, 9, 9, 10, 10, 1,
923 1, 2, 2, 4, 4, 11, 0, 11, 12, 12, 13, 13, 1, 1, 5, 5,
924 14, 14, 15, 16, 15, 16, 3, 3, 1, 6, 1, 6, 2, 2, 7, 7,
925 8, 8, 17, 17, 1, 1, 4, 4, 18, 18, 2, 2, 1, 19, 1, 20,
926 19, 20, 21, 21, 3, 3, 22, 22, 5, 5, 24, 1, 1, 23, 9, 23,
927 24, 9, 2, 2, 10, 1, 1, 10, 6, 6, 25, 4, 4, 25, 7, 7,
928 26, 8, 1, 8, 3, 1, 26, 3, 11, 11, 27, 27, 2, 28, 1, 2,
929 28, 1, 12, 12, 5, 5, 29, 13, 13, 29, 32, 1, 1, 33, 31, 30,
930 32, 4, 30, 33, 4, 31, 3, 14, 1, 1, 3, 34, 34, 2, 2, 14,
931 6, 6, 35, 36, 35, 36, 1, 15, 1, 16, 16, 15, 7, 9, 7, 9,
932 37, 8, 8, 37, 1, 1, 39, 2, 38, 39, 2, 40, 5, 38, 40, 5,
933 3, 3, 4, 4, 10, 10, 1, 1, 1, 1, 41, 2, 41, 2, 6, 6,
934 1, 1, 11, 42, 11, 43, 3, 42, 3, 17, 4, 43, 1, 17, 7, 1,
935 8, 44, 4, 7, 44, 5, 8, 2, 5, 1, 2, 48, 45, 1, 12, 45,
936 12, 48, 13, 13, 1, 9, 9, 46, 1, 46, 47, 47, 49, 18, 18, 49},
939 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 1, -1, 3, -3, 1,
940 -1, -2, 2, 1, -1, 1, -1, 4, -4, -2, 2, 1, -1, 1, -1, 5,
941 -5, -3, 3, 2, -2, 1, 0, -1, 1, -1, 1, -1, 6, -6, 2, -2,
942 1, -1, 1, 1, -1, -1, -3, 3, 7, 2, -7, -2, -4, 4, 2, -2,
943 2, -2, 1, -1, 8, -8, 3, -3, 1, -1, -5, 5, 9, 1, -9, 1,
944 -1, -1, 1, -1, -4, 4, 1, -1, 3, -3, 1, -10, 10, 1, 2, -1,
945 -1, -2, 6, -6, 2, 11, -11, -2, 3, -3, 1, -4, 4, -1, 3, -3,
946 1, 3, 12, -3, -5, -12, -1, 5, 2, -2, 1, -1, -7, 1, 13, 7,
947 -1, -13, 2, -2, 4, -4, 1, 2, -2, -1, 1, 14, -14, 1, 1, 1,
948 -1, -5, -1, -1, 5, -1, -6, 2, -15, 15, 6, 1, -1, -8, 8, -2,
949 -4, 4, 1, 1, -1, -1, 16, 2, -16, -2, 2, -2, 4, 3, -4, -3,
950 -1, -4, 4, 1, -17, 17, -1, -9, 1, 1, 9, 1, -5, -1, -1, 5,
951 -7, 7, 6, -6, 3, -3, 18, -18, 19, -19, 1, -10, -1, 10, -5, 5,
952 20, -20, -3, 1, 3, 1, 8, -1, -8, 2, 7, -1, -21, -2, 5, 21,
953 5, -1, -7, -5, 1, -6, -5, -11, 6, 22, 11, 1, 1, -22, -3, -1,
954 3, -1, 3, -3, -23, 4, -4, 1, 23, -1, 1, -1, 1, -2, 2, -1}
960 {1, 1, 1, 1, 0, 2, 2, 1, 1, 3, 3, 0, 1, 1, 2, 2,
961 4, 4, 1, 1, 5, 5, 1, 1, 2, 2, 3, 3, 6, 6, 1, 1,
962 7, 7, 8, 1, 8, 2, 2, 1, 4, 4, 1, 3, 1, 3, 9, 9,
963 2, 2, 1, 5, 1, 5, 10, 10, 1, 1, 11, 11, 3, 6, 3, 4,
964 4, 6, 2, 2, 1, 12, 1, 12, 7, 13, 7, 13, 1, 1, 8, 8,
965 2, 2, 14, 14, 16, 15, 16, 5, 5, 1, 3, 15, 1, 3, 4, 4,
966 1, 1, 17, 17, 2, 2, 6, 6, 1, 18, 1, 18, 22, 21, 22, 21,
967 25, 24, 25, 19, 9, 20, 9, 23, 19, 24, 20, 3, 23, 7, 3, 1,
968 1, 7, 28, 26, 29, 5, 28, 26, 5, 8, 29, 4, 8, 27, 2, 2,
969 4, 27, 1, 1, 10, 36, 10, 33, 33, 36, 30, 1, 32, 32, 1, 30,
970 6, 31, 31, 35, 3, 6, 11, 11, 3, 2, 35, 2, 34, 1, 34, 1,
971 37, 37, 12, 7, 12, 5, 41, 5, 4, 7, 1, 8, 13, 4, 1, 41,
972 13, 38, 8, 38, 9, 1, 40, 40, 9, 1, 39, 2, 2, 49, 39, 42,
973 3, 3, 14, 16, 49, 14, 16, 42, 43, 43, 6, 6, 15, 1, 1, 15,
974 44, 44, 1, 1, 50, 48, 4, 5, 4, 7, 5, 2, 10, 10, 48, 7,
975 50, 45, 2, 1, 45, 8, 8, 1, 46, 46, 3, 47, 47, 3, 1, 1},
978 { 1, -1, 2, -2, 0, 1, -1, 3, -3, 1, -1, 0, 4, -4, 2, -2,
979 1, -1, 5, -5, 1, -1, 6, -6, 3, -3, 2, -2, 1, -1, 7, -7,
980 1, -1, 1, 8, -1, 4, -4, -8, 2, -2, 9, 3, -9, -3, 1, -1,
981 5, -5, 10, 2, -10, -2, 1, -1, 11, -11, 1, -1, -4, 2, 4, 3,
982 -3, -2, 6, -6, 12, 1, -12, -1, 2, 1, -2, -1, 13, -13, 2, -2,
983 7, -7, 1, -1, 1, 1, -1, 3, -3, 14, 5, -1, -14, -5, 4, -4,
984 15, -15, 1, -1, 8, -8, -3, 3, 16, 1, -16, -1, 1, 1, -1, -1,
985 1, 1, -1, 1, 2, 1, -2, 1, -1, -1, -1, 6, -1, 3, -6, 17,
986 -17, -3, 1, 1, 1, 4, -1, -1, -4, 3, -1, 5, -3, -1, -9, 9,
987 -5, 1, 18, -18, 2, 1, -2, 1, -1, -1, 1, 19, -1, 1, -19, -1,
988 4, 1, -1, 1, 7, -4, -2, 2, -7, 10, -1, -10, 1, 20, -1, -20,
989 1, -1, 2, 4, -2, 5, 1, -5, 6, -4, 21, 4, 2, -6, -21, -1,
990 -2, 1, -4, -1, -3, 22, -1, 1, 3, -22, -1, 11, -11, 1, 1, 1,
991 8, -8, 2, 2, -1, -2, -2, -1, 1, -1, -5, 5, 2, 23, -23, -2,
992 1, -1, 24, -24, -1, -1, 7, 6, -7, 5, -6, 12, -3, 3, 1, -5,
993 1, 1, -12, 25, -1, -5, 5, -25, -1, 1, 9, 1, -1, -9, 26, -26}