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"
37 * Reverses "nbits" bits of the value "val" and returns the result
38 * in the least significant bits.
40 static uint16_t inv_bits(uint16_t val, int nbits)
45 res = av_reverse[val] >> (8-nbits);
47 res = ((av_reverse[val & 0xFF] << 8) + (av_reverse[val >> 8])) >> (16-nbits);
52 int ff_ivi_create_huff_from_desc(const IVIHuffDesc *cb, VLC *vlc, int flag)
54 int pos, i, j, codes_per_row, prefix, not_last_row;
55 uint16_t codewords[256]; /* FIXME: move this temporal storage out? */
58 pos = 0; /* current position = 0 */
60 for (i = 0; i < cb->num_rows; i++) {
61 codes_per_row = 1 << cb->xbits[i];
62 not_last_row = (i != cb->num_rows - 1);
63 prefix = ((1 << i) - 1) << (cb->xbits[i] + not_last_row);
65 for (j = 0; j < codes_per_row; j++) {
66 if (pos >= 256) /* Some Indeo5 codebooks can have more than 256 */
67 break; /* elements, but only 256 codes are allowed! */
69 bits[pos] = i + cb->xbits[i] + not_last_row;
70 if (bits[pos] > IVI_VLC_BITS)
71 return -1; /* invalid descriptor */
73 codewords[pos] = inv_bits((prefix | j), bits[pos]);
81 /* number of codewords = pos */
82 return init_vlc(vlc, IVI_VLC_BITS, pos, bits, 1, 1, codewords, 2, 2,
83 (flag & 1) | INIT_VLC_LE);
86 int ff_ivi_dec_huff_desc(GetBitContext *gb, IVIHuffDesc *desc)
90 tab_sel = get_bits(gb, 3);
92 /* custom huffman table (explicitly encoded) */
93 desc->num_rows = get_bits(gb, 4);
95 for (i = 0; i < desc->num_rows; i++)
96 desc->xbits[i] = get_bits(gb, 4);
102 int ff_ivi_huff_desc_cmp(const IVIHuffDesc *desc1, const IVIHuffDesc *desc2)
104 return desc1->num_rows != desc2->num_rows
105 || memcmp(desc1->xbits, desc2->xbits, desc1->num_rows);
108 void ff_ivi_huff_desc_copy(IVIHuffDesc *dst, const IVIHuffDesc *src)
110 dst->num_rows = src->num_rows;
111 memcpy(dst->xbits, src->xbits, src->num_rows);
114 int av_cold ff_ivi_init_planes(IVIPlaneDesc *planes, const IVIPicConfig *cfg)
117 uint32_t b_width, b_height, align_fac, width_aligned, height_aligned, buf_size;
120 ff_ivi_free_buffers(planes);
122 /* fill in the descriptor of the luminance plane */
123 planes[0].width = cfg->pic_width;
124 planes[0].height = cfg->pic_height;
125 planes[0].num_bands = cfg->luma_bands;
127 /* fill in the descriptors of the chrominance planes */
128 planes[1].width = planes[2].width = (cfg->pic_width + 3) >> 2;
129 planes[1].height = planes[2].height = (cfg->pic_height + 3) >> 2;
130 planes[1].num_bands = planes[2].num_bands = cfg->chroma_bands;
132 for (p = 0; p < 3; p++) {
133 planes[p].bands = av_mallocz(planes[p].num_bands * sizeof(IVIBandDesc));
134 if (!planes[p].bands)
135 return AVERROR(ENOMEM);
137 /* select band dimensions: if there is only one band then it
138 * has the full size, if there are several bands each of them
139 * has only half size */
140 b_width = planes[p].num_bands == 1 ? planes[p].width : (planes[p].width + 1) >> 1;
141 b_height = planes[p].num_bands == 1 ? planes[p].height : (planes[p].height + 1) >> 1;
143 /* luma band buffers will be aligned on 16x16 (max macroblock size) */
144 /* chroma band buffers will be aligned on 8x8 (max macroblock size) */
145 align_fac = p ? 8 : 16;
146 width_aligned = FFALIGN(b_width , align_fac);
147 height_aligned = FFALIGN(b_height, align_fac);
148 buf_size = width_aligned * height_aligned * sizeof(int16_t);
150 for (b = 0; b < planes[p].num_bands; b++) {
151 band = &planes[p].bands[b]; /* select appropriate plane/band */
154 band->width = b_width;
155 band->height = b_height;
156 band->pitch = width_aligned;
157 band->bufs[0] = av_malloc(buf_size);
158 band->bufs[1] = av_malloc(buf_size);
159 if (!band->bufs[0] || !band->bufs[1])
160 return AVERROR(ENOMEM);
162 /* allocate the 3rd band buffer for scalability mode */
163 if (cfg->luma_bands > 1) {
164 band->bufs[2] = av_malloc(buf_size);
166 return AVERROR(ENOMEM);
169 planes[p].bands[0].huff_desc.num_rows = 0; /* reset custom vlc */
176 void av_cold ff_ivi_free_buffers(IVIPlaneDesc *planes)
180 for (p = 0; p < 3; p++) {
181 for (b = 0; b < planes[p].num_bands; b++) {
182 av_freep(&planes[p].bands[b].bufs[0]);
183 av_freep(&planes[p].bands[b].bufs[1]);
184 av_freep(&planes[p].bands[b].bufs[2]);
186 for (t = 0; t < planes[p].bands[b].num_tiles; t++)
187 av_freep(&planes[p].bands[b].tiles[t].mbs);
188 av_freep(&planes[p].bands[b].tiles);
190 av_freep(&planes[p].bands);
194 int av_cold ff_ivi_init_tiles(IVIPlaneDesc *planes, int tile_width, int tile_height)
196 int p, b, x, y, x_tiles, y_tiles, t_width, t_height;
198 IVITile *tile, *ref_tile;
200 for (p = 0; p < 3; p++) {
201 t_width = !p ? tile_width : (tile_width + 3) >> 2;
202 t_height = !p ? tile_height : (tile_height + 3) >> 2;
204 for (b = 0; b < planes[p].num_bands; b++) {
205 band = &planes[p].bands[b];
206 x_tiles = IVI_NUM_TILES(band->width, t_width);
207 y_tiles = IVI_NUM_TILES(band->height, t_height);
208 band->num_tiles = x_tiles * y_tiles;
210 av_freep(&band->tiles);
211 band->tiles = av_mallocz(band->num_tiles * sizeof(IVITile));
213 return AVERROR(ENOMEM);
217 /* use the first luma band as reference for motion vectors
219 ref_tile = planes[0].bands[0].tiles;
221 for (y = 0; y < band->height; y += t_height) {
222 for (x = 0; x < band->width; x += t_width) {
225 tile->width = FFMIN(band->width - x, t_width);
226 tile->height = FFMIN(band->height - y, t_height);
227 tile->is_empty = tile->data_size = 0;
228 /* calculate number of macroblocks */
229 tile->num_MBs = IVI_MBs_PER_TILE(tile->width, tile->height,
232 av_freep(&tile->mbs);
233 tile->mbs = av_malloc(tile->num_MBs * sizeof(IVIMbInfo));
235 return AVERROR(ENOMEM);
239 tile->ref_mbs = ref_tile->mbs;
253 int ff_ivi_dec_tile_data_size(GetBitContext *gb)
259 len = get_bits(gb, 8);
261 len = get_bits_long(gb, 24);
264 /* align the bitstream reader on the byte boundary */
270 int ff_ivi_decode_blocks(GetBitContext *gb, IVIBandDesc *band, IVITile *tile)
272 int mbn, blk, num_blocks, num_coeffs, blk_size, scan_pos, run, val,
273 pos, is_intra, mc_type, mv_x, mv_y, col_mask;
274 uint8_t col_flags[8];
275 int32_t prev_dc, trvec[64];
276 uint32_t cbp, sym, lo, hi, quant, buf_offs, q;
278 RVMapDesc *rvmap = band->rv_map;
279 void (*mc_with_delta_func)(int16_t *buf, const int16_t *ref_buf, uint32_t pitch, int mc_type);
280 void (*mc_no_delta_func) (int16_t *buf, const int16_t *ref_buf, uint32_t pitch, int mc_type);
281 const uint8_t *base_tab, *scale_tab;
283 prev_dc = 0; /* init intra prediction for the DC coefficient */
285 blk_size = band->blk_size;
286 col_mask = blk_size - 1; /* column mask for tracking non-zero coeffs */
287 num_blocks = (band->mb_size != blk_size) ? 4 : 1; /* number of blocks per mb */
288 num_coeffs = blk_size * blk_size;
290 mc_with_delta_func = ff_ivi_mc_8x8_delta;
291 mc_no_delta_func = ff_ivi_mc_8x8_no_delta;
293 mc_with_delta_func = ff_ivi_mc_4x4_delta;
294 mc_no_delta_func = ff_ivi_mc_4x4_no_delta;
297 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
298 is_intra = !mb->type;
300 buf_offs = mb->buf_offs;
302 quant = av_clip(band->glob_quant + mb->q_delta, 0, 23);
304 base_tab = is_intra ? band->intra_base : band->inter_base;
305 scale_tab = is_intra ? band->intra_scale : band->inter_scale;
310 if (!band->is_halfpel) {
311 mc_type = 0; /* we have only fullpel vectors */
313 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
315 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
319 for (blk = 0; blk < num_blocks; blk++) {
320 /* adjust block position in the buffer according to its number */
322 buf_offs += blk_size;
323 } else if (blk == 2) {
324 buf_offs -= blk_size;
325 buf_offs += blk_size * band->pitch;
328 if (cbp & 1) { /* block coded ? */
330 memset(trvec, 0, num_coeffs*sizeof(trvec[0])); /* zero transform vector */
331 memset(col_flags, 0, sizeof(col_flags)); /* zero column flags */
333 while (scan_pos <= num_coeffs) {
334 sym = get_vlc2(gb, band->blk_vlc->table, IVI_VLC_BITS, 1);
335 if (sym == rvmap->eob_sym)
336 break; /* End of block */
338 if (sym == rvmap->esc_sym) { /* Escape - run/val explicitly coded using 3 vlc codes */
339 run = get_vlc2(gb, band->blk_vlc->table, IVI_VLC_BITS, 1) + 1;
340 lo = get_vlc2(gb, band->blk_vlc->table, IVI_VLC_BITS, 1);
341 hi = get_vlc2(gb, band->blk_vlc->table, IVI_VLC_BITS, 1);
342 val = IVI_TOSIGNED((hi << 6) | lo); /* merge them and convert into signed val */
344 run = rvmap->runtab[sym];
345 val = rvmap->valtab[sym];
348 /* de-zigzag and dequantize */
350 if (scan_pos >= num_coeffs)
352 pos = band->scan[scan_pos];
354 if (IVI_DEBUG && !val)
355 av_log(NULL, AV_LOG_ERROR, "Val = 0 encountered!\n");
357 q = (base_tab[pos] * scale_tab[quant]) >> 8;
359 val = val * q + FFSIGN(val) * ((q >> 1) - (q & 1));
361 col_flags[pos & col_mask] |= val; /* track columns containing non-zero coeffs */
364 if (scan_pos >= num_coeffs && sym != rvmap->eob_sym)
365 return -1; /* corrupt block data */
367 /* undoing DC coeff prediction for intra-blocks */
368 if (is_intra && band->is_2d_trans) {
371 col_flags[0] |= !!prev_dc;
374 /* apply inverse transform */
375 band->inv_transform(trvec, band->buf + buf_offs,
376 band->pitch, col_flags);
378 /* apply motion compensation */
380 mc_with_delta_func(band->buf + buf_offs,
381 band->ref_buf + buf_offs + mv_y * band->pitch + mv_x,
382 band->pitch, mc_type);
384 /* block not coded */
385 /* for intra blocks apply the dc slant transform */
386 /* for inter - perform the motion compensation without delta */
387 if (is_intra && band->dc_transform) {
388 band->dc_transform(&prev_dc, band->buf + buf_offs,
389 band->pitch, blk_size);
391 mc_no_delta_func(band->buf + buf_offs,
392 band->ref_buf + buf_offs + mv_y * band->pitch + mv_x,
393 band->pitch, mc_type);
405 void ff_ivi_process_empty_tile(AVCodecContext *avctx, IVIBandDesc *band,
406 IVITile *tile, int32_t mv_scale)
408 int x, y, need_mc, mbn, blk, num_blocks, mv_x, mv_y, mc_type;
409 int offs, mb_offset, row_offset;
410 IVIMbInfo *mb, *ref_mb;
413 void (*mc_no_delta_func)(int16_t *buf, const int16_t *ref_buf, uint32_t pitch,
416 offs = tile->ypos * band->pitch + tile->xpos;
418 ref_mb = tile->ref_mbs;
419 row_offset = band->mb_size * band->pitch;
420 need_mc = 0; /* reset the mc tracking flag */
422 for (y = tile->ypos; y < (tile->ypos + tile->height); y += band->mb_size) {
425 for (x = tile->xpos; x < (tile->xpos + tile->width); x += band->mb_size) {
428 mb->buf_offs = mb_offset;
430 mb->type = 1; /* set the macroblocks type = INTER */
431 mb->cbp = 0; /* all blocks are empty */
433 if (!band->qdelta_present && !band->plane && !band->band_num) {
434 mb->q_delta = band->glob_quant;
439 if (band->inherit_qdelta && ref_mb)
440 mb->q_delta = ref_mb->q_delta;
442 if (band->inherit_mv) {
443 /* motion vector inheritance */
445 mb->mv_x = ivi_scale_mv(ref_mb->mv_x, mv_scale);
446 mb->mv_y = ivi_scale_mv(ref_mb->mv_y, mv_scale);
448 mb->mv_x = ref_mb->mv_x;
449 mb->mv_y = ref_mb->mv_y;
451 need_mc |= mb->mv_x || mb->mv_y; /* tracking non-zero motion vectors */
457 mb_offset += band->mb_size;
462 if (band->inherit_mv && need_mc) { /* apply motion compensation if there is at least one non-zero motion vector */
463 num_blocks = (band->mb_size != band->blk_size) ? 4 : 1; /* number of blocks per mb */
464 mc_no_delta_func = (band->blk_size == 8) ? ff_ivi_mc_8x8_no_delta
465 : ff_ivi_mc_4x4_no_delta;
467 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
470 if (!band->is_halfpel) {
471 mc_type = 0; /* we have only fullpel vectors */
473 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
475 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
478 for (blk = 0; blk < num_blocks; blk++) {
479 /* adjust block position in the buffer according with its number */
480 offs = mb->buf_offs + band->blk_size * ((blk & 1) + !!(blk & 2) * band->pitch);
481 mc_no_delta_func(band->buf + offs,
482 band->ref_buf + offs + mv_y * band->pitch + mv_x,
483 band->pitch, mc_type);
487 /* copy data from the reference tile into the current one */
488 src = band->ref_buf + tile->ypos * band->pitch + tile->xpos;
489 dst = band->buf + tile->ypos * band->pitch + tile->xpos;
490 for (y = 0; y < tile->height; y++) {
491 memcpy(dst, src, tile->width*sizeof(band->buf[0]));
500 uint16_t ivi_calc_band_checksum (IVIBandDesc *band)
503 int16_t *src, checksum;
508 for (y = 0; y < band->height; src += band->pitch, y++)
509 for (x = 0; x < band->width; x++)
515 int ivi_check_band (IVIBandDesc *band, const uint8_t *ref, int pitch)
524 for (y = 0; y < band->height; src += band->pitch, y++) {
525 for (x = 0; x < band->width; x++) {
526 t1 = av_clip(src[x] + 128, 0, 255);
529 av_log(NULL, AV_LOG_ERROR, "Data mismatch: row %d, column %d\n",
530 y / band->blk_size, x / band->blk_size);
541 void ff_ivi_output_plane(IVIPlaneDesc *plane, uint8_t *dst, int dst_pitch)
544 const int16_t *src = plane->bands[0].buf;
545 uint32_t pitch = plane->bands[0].pitch;
547 for (y = 0; y < plane->height; y++) {
548 for (x = 0; x < plane->width; x++)
549 dst[x] = av_clip_uint8(src[x] + 128);
557 * These are 2x8 predefined Huffman codebooks for coding macroblock/block
558 * signals. They are specified using "huffman descriptors" in order to
559 * avoid huge static tables. The decoding tables will be generated at
560 * startup from these descriptors.
562 const IVIHuffDesc ff_ivi_mb_huff_desc[8] = {
563 {8, {0, 4, 5, 4, 4, 4, 6, 6}},
564 {12, {0, 2, 2, 3, 3, 3, 3, 5, 3, 2, 2, 2}},
565 {12, {0, 2, 3, 4, 3, 3, 3, 3, 4, 3, 2, 2}},
566 {12, {0, 3, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2}},
567 {13, {0, 4, 4, 3, 3, 3, 3, 2, 3, 3, 2, 1, 1}},
568 {9, {0, 4, 4, 4, 4, 3, 3, 3, 2}},
569 {10, {0, 4, 4, 4, 4, 3, 3, 2, 2, 2}},
570 {12, {0, 4, 4, 4, 3, 3, 2, 3, 2, 2, 2, 2}}
573 const IVIHuffDesc ff_ivi_blk_huff_desc[8] = {
574 {10, {1, 2, 3, 4, 4, 7, 5, 5, 4, 1}},
575 {11, {2, 3, 4, 4, 4, 7, 5, 4, 3, 3, 2}},
576 {12, {2, 4, 5, 5, 5, 5, 6, 4, 4, 3, 1, 1}},
577 {13, {3, 3, 4, 4, 5, 6, 6, 4, 4, 3, 2, 1, 1}},
578 {11, {3, 4, 4, 5, 5, 5, 6, 5, 4, 2, 2}},
579 {13, {3, 4, 5, 5, 5, 5, 6, 4, 3, 3, 2, 1, 1}},
580 {13, {3, 4, 5, 5, 5, 6, 5, 4, 3, 3, 2, 1, 1}},
581 {9, {3, 4, 4, 5, 5, 5, 6, 5, 5}}
586 * Run-value (RLE) tables.
588 const RVMapDesc ff_ivi_rvmap_tabs[9] = {
593 {1, 1, 0, 1, 1, 0, 1, 1, 2, 2, 1, 1, 1, 1, 3, 3,
594 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 1, 1, 2, 2, 5, 5,
595 1, 1, 3, 3, 1, 1, 6, 6, 1, 2, 1, 2, 7, 7, 1, 1,
596 8, 8, 1, 1, 4, 2, 1, 4, 2, 1, 3, 3, 1, 1, 1, 9,
597 9, 1, 2, 1, 2, 1, 5, 5, 1, 1, 10, 10, 1, 1, 3, 3,
598 2, 2, 1, 1, 11, 11, 6, 4, 4, 1, 6, 1, 2, 1, 2, 12,
599 8, 1, 12, 7, 8, 7, 1, 16, 1, 16, 1, 3, 3, 13, 1, 13,
600 2, 2, 1, 15, 1, 5, 14, 15, 1, 5, 14, 1, 17, 8, 17, 8,
601 1, 4, 4, 2, 2, 1, 25, 25, 24, 24, 1, 3, 1, 3, 1, 8,
602 6, 7, 6, 1, 18, 8, 18, 1, 7, 23, 2, 2, 23, 1, 1, 21,
603 22, 9, 9, 22, 19, 1, 21, 5, 19, 5, 1, 33, 20, 33, 20, 8,
604 4, 4, 1, 32, 2, 2, 8, 3, 32, 26, 3, 1, 7, 7, 26, 6,
605 1, 6, 1, 1, 16, 1, 10, 1, 10, 2, 16, 29, 28, 2, 29, 28,
606 1, 27, 5, 8, 5, 27, 1, 8, 3, 7, 3, 31, 41, 31, 1, 41,
607 6, 1, 6, 7, 4, 4, 1, 1, 2, 1, 2, 11, 34, 30, 11, 1,
608 30, 15, 15, 34, 36, 40, 36, 40, 35, 35, 37, 37, 39, 39, 38, 38},
611 { 1, -1, 0, 2, -2, 0, 3, -3, 1, -1, 4, -4, 5, -5, 1, -1,
612 6, -6, 2, -2, 7, -7, 1, -1, 8, -8, 9, -9, 3, -3, 1, -1,
613 10, -10, 2, -2, 11, -11, 1, -1, 12, 4, -12, -4, 1, -1, 13, -13,
614 1, -1, 14, -14, 2, 5, 15, -2, -5, -15, -3, 3, 16, -16, 17, 1,
615 -1, -17, 6, 18, -6, -18, 2, -2, 19, -19, 1, -1, 20, -20, 4, -4,
616 7, -7, 21, -21, 1, -1, 2, 3, -3, 22, -2, -22, 8, 23, -8, 1,
617 2, -23, -1, 2, -2, -2, 24, 1, -24, -1, 25, 5, -5, 1, -25, -1,
618 9, -9, 26, 1, -26, 3, 1, -1, 27, -3, -1, -27, 1, 3, -1, -3,
619 28, -4, 4, 10, -10, -28, 1, -1, 1, -1, 29, 6, -29, -6, 30, -4,
620 3, 3, -3, -30, 1, 4, -1, 31, -3, 1, 11, -11, -1, -31, 32, -1,
621 -1, 2, -2, 1, 1, -32, 1, 4, -1, -4, 33, -1, 1, 1, -1, 5,
622 5, -5, -33, -1, -12, 12, -5, -7, 1, 1, 7, 34, 4, -4, -1, 4,
623 -34, -4, 35, 36, -2, -35, -2, -36, 2, 13, 2, -1, 1, -13, 1, -1,
624 37, 1, -5, 6, 5, -1, 38, -6, -8, 5, 8, -1, 1, 1, -37, -1,
625 5, 39, -5, -5, 6, -6, -38, -39, -14, 40, 14, 2, 1, 1, -2, -40,
626 -1, -2, 2, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1}
632 {0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 8, 6, 8, 7,
633 7, 9, 9, 10, 10, 11, 11, 1, 12, 1, 12, 13, 13, 16, 14, 16,
634 14, 15, 15, 17, 17, 18, 0, 18, 19, 20, 21, 19, 22, 21, 20, 22,
635 25, 24, 2, 25, 24, 23, 23, 2, 26, 28, 26, 28, 29, 27, 29, 27,
636 33, 33, 1, 32, 1, 3, 32, 30, 36, 3, 36, 30, 31, 31, 35, 34,
637 37, 41, 34, 35, 37, 4, 41, 4, 49, 8, 8, 49, 40, 38, 5, 38,
638 40, 39, 5, 39, 42, 43, 42, 7, 57, 6, 43, 44, 6, 50, 7, 44,
639 57, 48, 50, 48, 45, 45, 46, 47, 51, 46, 47, 58, 1, 51, 58, 1,
640 52, 59, 53, 9, 52, 55, 55, 59, 53, 56, 54, 56, 54, 9, 64, 64,
641 60, 63, 60, 63, 61, 62, 61, 62, 2, 10, 2, 10, 11, 1, 11, 13,
642 12, 1, 12, 13, 16, 16, 8, 8, 14, 3, 3, 15, 14, 15, 4, 4,
643 1, 17, 17, 5, 1, 7, 7, 5, 6, 1, 2, 2, 6, 22, 1, 25,
644 21, 22, 8, 24, 1, 21, 25, 24, 8, 18, 18, 23, 9, 20, 23, 33,
645 29, 33, 20, 1, 19, 1, 29, 36, 9, 36, 19, 41, 28, 57, 32, 3,
646 28, 3, 1, 27, 49, 49, 1, 32, 26, 26, 2, 4, 4, 7, 57, 41,
647 2, 7, 10, 5, 37, 16, 10, 27, 8, 8, 13, 16, 37, 13, 1, 5},
650 {0, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1,
651 -1, 1, -1, 1, -1, 1, -1, 2, 1, -2, -1, 1, -1, 1, 1, -1,
652 -1, 1, -1, 1, -1, 1, 0, -1, 1, 1, 1, -1, 1, -1, -1, -1,
653 1, 1, 2, -1, -1, 1, -1, -2, 1, 1, -1, -1, 1, 1, -1, -1,
654 1, -1, 3, 1, -3, 2, -1, 1, 1, -2, -1, -1, -1, 1, 1, 1,
655 1, 1, -1, -1, -1, 2, -1, -2, 1, 2, -2, -1, 1, 1, 2, -1,
656 -1, 1, -2, -1, 1, 1, -1, 2, 1, 2, -1, 1, -2, -1, -2, -1,
657 -1, 1, 1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 4, -1, -1, -4,
658 1, 1, 1, 2, -1, -1, 1, -1, -1, 1, -1, -1, 1, -2, 1, -1,
659 1, 1, -1, -1, 1, 1, -1, -1, 3, 2, -3, -2, 2, 5, -2, 2,
660 2, -5, -2, -2, -2, 2, -3, 3, 2, 3, -3, 2, -2, -2, 3, -3,
661 6, 2, -2, 3, -6, 3, -3, -3, 3, 7, -4, 4, -3, 2, -7, 2,
662 2, -2, -4, 2, 8, -2, -2, -2, 4, 2, -2, 2, 3, 2, -2, -2,
663 2, 2, -2, -8, -2, 9, -2, 2, -3, -2, 2, -2, 2, 2, 2, 4,
664 -2, -4, 10, 2, 2, -2, -9, -2, 2, -2, 5, 4, -4, 4, -2, 2,
665 -5, -4, -3, 4, 2, -3, 3, -2, -5, 5, 3, 3, -2, -3, -10, -4}
671 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 0, 1, 1, 5, 5,
672 2, 2, 6, 6, 7, 7, 1, 8, 1, 8, 3, 3, 9, 9, 1, 2,
673 2, 1, 4, 10, 4, 10, 11, 11, 1, 5, 12, 12, 1, 5, 13, 13,
674 3, 3, 6, 6, 2, 2, 14, 14, 16, 16, 15, 7, 15, 8, 8, 7,
675 1, 1, 17, 17, 4, 4, 1, 1, 18, 18, 2, 2, 5, 5, 25, 3,
676 9, 3, 25, 9, 19, 24, 19, 24, 1, 21, 20, 1, 21, 22, 20, 22,
677 23, 23, 8, 6, 33, 6, 8, 33, 7, 7, 26, 26, 1, 32, 1, 32,
678 28, 4, 28, 10, 29, 27, 27, 10, 41, 4, 29, 2, 2, 41, 36, 31,
679 49, 31, 34, 30, 34, 36, 30, 35, 1, 49, 11, 5, 35, 11, 1, 3,
680 3, 5, 37, 37, 8, 40, 8, 40, 12, 12, 42, 42, 1, 38, 16, 57,
681 1, 6, 16, 39, 38, 6, 7, 7, 13, 13, 39, 43, 2, 43, 57, 2,
682 50, 9, 44, 9, 50, 4, 15, 48, 44, 4, 1, 15, 48, 14, 14, 1,
683 45, 45, 8, 3, 5, 8, 51, 47, 3, 46, 46, 47, 5, 51, 1, 17,
684 17, 58, 1, 58, 2, 52, 52, 2, 53, 7, 59, 6, 6, 56, 53, 55,
685 7, 55, 1, 54, 59, 56, 54, 10, 1, 10, 4, 60, 1, 60, 8, 4,
686 8, 64, 64, 61, 1, 63, 3, 63, 62, 61, 5, 11, 5, 3, 11, 62},
689 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 0, 3, -3, 1, -1,
690 2, -2, 1, -1, 1, -1, 4, 1, -4, -1, 2, -2, 1, -1, 5, 3,
691 -3, -5, 2, 1, -2, -1, 1, -1, 6, 2, 1, -1, -6, -2, 1, -1,
692 3, -3, 2, -2, 4, -4, 1, -1, 1, -1, 1, 2, -1, 2, -2, -2,
693 7, -7, 1, -1, 3, -3, 8, -8, 1, -1, 5, -5, 3, -3, 1, 4,
694 2, -4, -1, -2, 1, 1, -1, -1, 9, 1, 1, -9, -1, 1, -1, -1,
695 1, -1, 3, -3, 1, 3, -3, -1, 3, -3, 1, -1, 10, 1, -10, -1,
696 1, 4, -1, 2, 1, -1, 1, -2, 1, -4, -1, 6, -6, -1, 1, 1,
697 1, -1, 1, 1, -1, -1, -1, 1, 11, -1, -2, 4, -1, 2, -11, 5,
698 -5, -4, -1, 1, 4, 1, -4, -1, -2, 2, 1, -1, 12, 1, -2, 1,
699 -12, 4, 2, 1, -1, -4, 4, -4, 2, -2, -1, 1, 7, -1, -1, -7,
700 -1, -3, 1, 3, 1, 5, 2, 1, -1, -5, 13, -2, -1, 2, -2, -13,
701 1, -1, 5, 6, 5, -5, 1, 1, -6, 1, -1, -1, -5, -1, 14, 2,
702 -2, 1, -14, -1, 8, 1, -1, -8, 1, 5, 1, 5, -5, 1, -1, 1,
703 -5, -1, 15, 1, -1, -1, -1, 3, -15, -3, 6, 1, 16, -1, 6, -6,
704 -6, 1, -1, 1, -16, 1, 7, -1, 1, -1, -6, -3, 6, -7, 3, -1}
710 {0, 1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6, 6, 7,
711 7, 8, 8, 9, 9, 2, 2, 10, 10, 1, 1, 11, 11, 12, 12, 3,
712 3, 13, 13, 0, 14, 14, 16, 15, 16, 15, 4, 4, 17, 1, 17, 1,
713 5, 5, 18, 18, 2, 2, 6, 6, 8, 19, 7, 8, 7, 19, 20, 20,
714 21, 21, 22, 24, 22, 24, 23, 23, 1, 1, 25, 25, 3, 3, 26, 26,
715 9, 9, 27, 27, 28, 28, 33, 29, 4, 33, 29, 1, 4, 1, 32, 32,
716 2, 2, 31, 10, 30, 10, 30, 31, 34, 34, 5, 5, 36, 36, 35, 41,
717 35, 11, 41, 11, 37, 1, 8, 8, 37, 6, 1, 6, 40, 7, 7, 40,
718 12, 38, 12, 39, 39, 38, 49, 13, 49, 13, 3, 42, 3, 42, 16, 16,
719 43, 43, 14, 14, 1, 1, 44, 15, 44, 15, 2, 2, 57, 48, 50, 48,
720 57, 50, 4, 45, 45, 4, 46, 47, 47, 46, 1, 51, 1, 17, 17, 51,
721 8, 9, 9, 5, 58, 8, 58, 5, 52, 52, 55, 56, 53, 56, 55, 59,
722 59, 53, 54, 1, 6, 54, 7, 7, 6, 1, 2, 3, 2, 3, 64, 60,
723 60, 10, 10, 64, 61, 62, 61, 63, 1, 63, 62, 1, 18, 24, 18, 4,
724 25, 4, 8, 21, 21, 1, 24, 22, 25, 22, 8, 11, 19, 11, 23, 1,
725 20, 23, 19, 20, 5, 12, 5, 1, 16, 2, 12, 13, 2, 13, 1, 16},
728 { 0, 1, -1, 1, -1, 1, -1, 1, -1, 2, -2, 1, -1, 1, -1, 1,
729 -1, 1, -1, 1, -1, 2, -2, 1, -1, 3, -3, 1, -1, 1, -1, 2,
730 -2, 1, -1, 0, 1, -1, 1, 1, -1, -1, 2, -2, 1, 4, -1, -4,
731 2, -2, 1, -1, -3, 3, 2, -2, 2, 1, 2, -2, -2, -1, 1, -1,
732 1, -1, 1, 1, -1, -1, 1, -1, 5, -5, 1, -1, 3, -3, 1, -1,
733 2, -2, 1, -1, 1, -1, 1, 1, 3, -1, -1, 6, -3, -6, -1, 1,
734 4, -4, 1, 2, 1, -2, -1, -1, 1, -1, 3, -3, 1, -1, 1, 1,
735 -1, 2, -1, -2, 1, 7, -3, 3, -1, 3, -7, -3, 1, -3, 3, -1,
736 2, 1, -2, 1, -1, -1, 1, 2, -1, -2, -4, -1, 4, 1, 2, -2,
737 1, -1, -2, 2, 8, -8, -1, 2, 1, -2, -5, 5, 1, -1, -1, 1,
738 -1, 1, 4, -1, 1, -4, -1, -1, 1, 1, 9, 1, -9, 2, -2, -1,
739 -4, 3, -3, -4, -1, 4, 1, 4, 1, -1, 1, -1, 1, 1, -1, 1,
740 -1, -1, -1, 10, 4, 1, 4, -4, -4, -10, 6, 5, -6, -5, 1, -1,
741 1, 3, -3, -1, 1, -1, -1, -1, 11, 1, 1, -11, -2, -2, 2, 5,
742 -2, -5, -5, 2, -2, 12, 2, -2, 2, 2, 5, -3, -2, 3, -2, -12,
743 -2, 2, 2, 2, -5, 3, 5, 13, -3, 7, -3, -3, -7, 3, -13, 3}
749 {0, 1, 1, 1, 2, 2, 1, 3, 3, 1, 1, 1, 4, 4, 1, 5,
750 2, 1, 5, 2, 1, 1, 6, 6, 1, 1, 1, 1, 1, 7, 3, 1,
751 2, 3, 0, 1, 2, 7, 1, 1, 1, 8, 1, 1, 8, 1, 1, 1,
752 9, 1, 9, 1, 2, 1, 1, 2, 1, 1, 10, 4, 1, 10, 1, 4,
753 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 2, 1, 5, 1, 1, 1,
754 2, 5, 1, 11, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
755 2, 1, 6, 1, 6, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 12,
756 3, 1, 12, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1,
757 4, 1, 1, 1, 2, 1, 1, 4, 1, 1, 1, 1, 1, 1, 2, 1,
758 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 5,
759 1, 1, 1, 1, 1, 7, 1, 7, 1, 1, 2, 3, 1, 1, 1, 1,
760 5, 1, 1, 1, 1, 1, 1, 2, 13, 1, 1, 1, 1, 1, 1, 1,
761 1, 1, 1, 1, 1, 1, 1, 1, 13, 2, 1, 1, 4, 1, 1, 1,
762 3, 1, 6, 1, 1, 1, 14, 1, 1, 1, 1, 1, 14, 6, 1, 1,
763 1, 1, 15, 2, 4, 1, 2, 3, 15, 1, 1, 1, 8, 1, 1, 8,
764 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1},
767 { 0, 1, -1, 2, 1, -1, -2, 1, -1, 3, -3, 4, 1, -1, -4, 1,
768 2, 5, -1, -2, -5, 6, 1, -1, -6, 7, -7, 8, -8, 1, 2, 9,
769 3, -2, 0, -9, -3, -1, 10, -10, 11, 1, -11, 12, -1, -12, 13, -13,
770 1, 14, -1, -14, 4, 15, -15, -4, 16, -16, 1, 2, 17, -1, -17, -2,
771 18, -18, 19, -19, 20, 3, -20, 21, -21, -3, 5, 22, 2, -22, -23, 23,
772 -5, -2, 24, 1, -24, -1, 25, -25, 26, -26, -27, 27, 28, 29, -28, -29,
773 6, 30, 2, -31, -2, -30, 31, -6, -32, 32, 33, -33, 34, -35, -34, 1,
774 4, -36, -1, 35, 37, 36, 7, -37, 38, -4, -38, 39, 41, 40, -40, -39,
775 3, 42, -43, -41, -7, -42, 43, -3, 44, -44, 45, -45, 46, 47, 8, -47,
776 -48, -46, 50, -50, 48, 49, 51, -49, 52, -52, 5, -51, -8, -53, 53, 3,
777 -56, 56, 55, 54, -54, 2, 60, -2, -55, 58, 9, -5, 59, 57, -57, -63,
778 -3, -58, -60, -61, 61, -59, -62, -9, 1, 64, 62, 69, -64, 63, 65, -67,
779 -68, 66, -65, 68, -66, -69, 67, -70, -1, 10, 71, -71, 4, 73, 72, 70,
780 6, -76, -3, 74, -78, -74, 1, 78, 80, -72, -75, 76, -1, 3, -73, 79,
781 75, 77, 1, 11, -4, -79, -10, -6, -1, -77, -83, -80, 2, 81, -84, -2,
782 83, -81, 82, -82, 84, -87, -86, 85, -11, -85, 86, -89, 87, -88, 88, 89}
788 {1, 1, 0, 2, 1, 2, 1, 3, 3, 1, 1, 4, 4, 2, 2, 1,
789 1, 5, 5, 6, 1, 6, 1, 7, 7, 3, 3, 2, 8, 2, 8, 1,
790 1, 0, 9, 9, 1, 1, 10, 4, 10, 4, 11, 11, 2, 1, 2, 1,
791 12, 12, 3, 3, 1, 1, 13, 5, 5, 13, 14, 1, 1, 14, 2, 2,
792 6, 6, 15, 1, 1, 15, 16, 4, 7, 16, 4, 7, 1, 1, 3, 3,
793 8, 8, 2, 2, 1, 1, 17, 17, 1, 1, 18, 18, 5, 5, 2, 2,
794 1, 1, 9, 19, 9, 19, 20, 3, 3, 20, 1, 10, 21, 1, 10, 4,
795 4, 21, 22, 6, 6, 22, 1, 1, 23, 24, 2, 2, 23, 24, 11, 1,
796 1, 11, 7, 25, 7, 1, 1, 25, 8, 8, 3, 26, 3, 1, 12, 2,
797 2, 26, 1, 12, 5, 5, 27, 4, 1, 4, 1, 27, 28, 1, 28, 13,
798 1, 13, 2, 29, 2, 1, 32, 6, 1, 30, 14, 29, 14, 6, 3, 31,
799 3, 1, 30, 1, 32, 31, 33, 9, 33, 1, 1, 7, 9, 7, 2, 2,
800 1, 1, 4, 36, 34, 4, 5, 10, 10, 5, 34, 1, 1, 35, 8, 8,
801 36, 3, 35, 1, 15, 3, 2, 1, 16, 15, 16, 2, 37, 1, 37, 1,
802 1, 1, 6, 6, 38, 1, 38, 11, 1, 39, 39, 40, 11, 2, 41, 4,
803 40, 1, 2, 4, 1, 1, 1, 41, 3, 1, 3, 1, 5, 7, 5, 7},
806 { 1, -1, 0, 1, 2, -1, -2, 1, -1, 3, -3, 1, -1, 2, -2, 4,
807 -4, 1, -1, 1, 5, -1, -5, 1, -1, 2, -2, 3, 1, -3, -1, 6,
808 -6, 0, 1, -1, 7, -7, 1, 2, -1, -2, 1, -1, 4, 8, -4, -8,
809 1, -1, 3, -3, 9, -9, 1, 2, -2, -1, 1, 10, -10, -1, 5, -5,
810 2, -2, 1, 11, -11, -1, 1, 3, 2, -1, -3, -2, 12, -12, 4, -4,
811 2, -2, -6, 6, 13, -13, 1, -1, 14, -14, 1, -1, 3, -3, 7, -7,
812 15, -15, 2, 1, -2, -1, 1, 5, -5, -1, -16, 2, 1, 16, -2, 4,
813 -4, -1, 1, 3, -3, -1, 17, -17, 1, 1, -8, 8, -1, -1, 2, 18,
814 -18, -2, 3, 1, -3, 19, -19, -1, 3, -3, 6, 1, -6, 20, 2, 9,
815 -9, -1, -20, -2, 4, -4, 1, -5, 21, 5, -21, -1, 1, -22, -1, 2,
816 22, -2, 10, 1, -10, 23, 1, 4, -23, 1, 2, -1, -2, -4, -7, 1,
817 7, -24, -1, 24, -1, -1, 1, 3, -1, -25, 25, 4, -3, -4, 11, -11,
818 26, -26, 6, 1, 1, -6, -5, -3, 3, 5, -1, -27, 27, 1, 4, -4,
819 -1, -8, -1, 28, 2, 8, -12, -28, -2, -2, 2, 12, -1, 29, 1, -29,
820 30, -30, 5, -5, 1, -31, -1, 3, 31, -1, 1, 1, -3, -13, 1, -7,
821 -1, -32, 13, 7, 32, 33, -33, -1, -9, -34, 9, 34, -6, 5, 6, -5}
827 {1, 1, 0, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 0, 2, 2,
828 4, 1, 4, 1, 1, 1, 5, 5, 1, 1, 6, 6, 2, 2, 1, 1,
829 3, 3, 7, 7, 1, 1, 8, 8, 1, 1, 2, 2, 1, 9, 1, 9,
830 4, 4, 10, 1, 1, 10, 1, 1, 11, 11, 3, 3, 1, 2, 1, 2,
831 1, 1, 12, 12, 5, 5, 1, 1, 13, 1, 1, 13, 2, 2, 1, 1,
832 6, 6, 1, 1, 4, 14, 4, 14, 3, 1, 3, 1, 1, 1, 15, 7,
833 15, 2, 2, 7, 1, 1, 1, 8, 1, 8, 16, 16, 1, 1, 1, 1,
834 2, 1, 1, 2, 1, 1, 3, 5, 5, 3, 4, 1, 1, 4, 1, 1,
835 17, 17, 9, 1, 1, 9, 2, 2, 1, 1, 10, 10, 1, 6, 1, 1,
836 6, 18, 1, 1, 18, 1, 1, 1, 2, 2, 3, 1, 3, 1, 1, 1,
837 4, 1, 19, 1, 19, 7, 1, 1, 20, 1, 4, 20, 1, 7, 11, 2,
838 1, 11, 21, 2, 8, 5, 1, 8, 1, 5, 21, 1, 1, 1, 22, 1,
839 1, 22, 1, 1, 3, 3, 1, 23, 2, 12, 24, 1, 1, 2, 1, 1,
840 12, 23, 1, 1, 24, 1, 1, 1, 4, 1, 1, 1, 2, 1, 6, 6,
841 4, 2, 1, 1, 1, 1, 1, 1, 1, 14, 13, 3, 1, 25, 9, 25,
842 14, 1, 9, 3, 13, 1, 1, 1, 1, 1, 10, 1, 1, 2, 10, 2},
845 {-20, -1, 0, 2, -2, 1, -1, 3, -3, 1, -1, 4, -4, 0, 2, -2,
846 1, 5, -1, -5, 6, -6, 1, -1, 7, -7, 1, -1, 3, -3, 8, -8,
847 2, -2, 1, -1, 9, -9, 1, -1, 10, -10, 4, -4, 11, 1, -11, -1,
848 2, -2, 1, 12, -12, -1, 13, -13, 1, -1, 3, -3, 14, 5, -14, -5,
849 -15, 15, -1, 1, 2, -2, 16, -16, 1, 17, -17, -1, 6, -6, 18, -18,
850 2, -2, -19, 19, -3, 1, 3, -1, 4, 20, -4, 1, -21, 21, 1, 2,
851 -1, -7, 7, -2, 22, -22, 23, 2, -23, -2, 1, -1, -24, 24, -25, 25,
852 -8, -26, 26, 8, -27, 27, 5, 3, -3, -5, -4, 28, -28, 4, 29, -29,
853 1, -1, -2, -30, 30, 2, 9, -9, -31, 31, 2, -2, -32, 3, 32, -33,
854 -3, 1, 33, -34, -1, 34, -35, 35, -10, 10, -6, 36, 6, -36, 37, -37,
855 -5, 38, 1, -38, -1, 3, 39, -39, -1, 40, 5, 1, -40, -3, 2, -11,
856 -41, -2, 1, 11, -3, -4, 41, 3, 42, 4, -1, -43, -42, 43, 1, -44,
857 45, -1, 44, -45, -7, 7, -46, 1, -12, 2, 1, -47, 46, 12, 47, 48,
858 -2, -1, -48, 49, -1, -50, -49, 50, -6, -51, 51, 52, -13, 53, -4, 4,
859 6, 13, -53, -52, -54, 55, 54, -55, -56, -2, 2, -8, 56, 1, -3, -1,
860 2, 58, 3, 8, -2, 57, -58, -60, -59, -57, -3, 60, 59, -14, 3, 14}
866 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 5, 5, 1, 1, 6,
867 6, 2, 2, 7, 7, 8, 8, 1, 1, 3, 3, 9, 9, 10, 10, 1,
868 1, 2, 2, 4, 4, 11, 0, 11, 12, 12, 13, 13, 1, 1, 5, 5,
869 14, 14, 15, 16, 15, 16, 3, 3, 1, 6, 1, 6, 2, 2, 7, 7,
870 8, 8, 17, 17, 1, 1, 4, 4, 18, 18, 2, 2, 1, 19, 1, 20,
871 19, 20, 21, 21, 3, 3, 22, 22, 5, 5, 24, 1, 1, 23, 9, 23,
872 24, 9, 2, 2, 10, 1, 1, 10, 6, 6, 25, 4, 4, 25, 7, 7,
873 26, 8, 1, 8, 3, 1, 26, 3, 11, 11, 27, 27, 2, 28, 1, 2,
874 28, 1, 12, 12, 5, 5, 29, 13, 13, 29, 32, 1, 1, 33, 31, 30,
875 32, 4, 30, 33, 4, 31, 3, 14, 1, 1, 3, 34, 34, 2, 2, 14,
876 6, 6, 35, 36, 35, 36, 1, 15, 1, 16, 16, 15, 7, 9, 7, 9,
877 37, 8, 8, 37, 1, 1, 39, 2, 38, 39, 2, 40, 5, 38, 40, 5,
878 3, 3, 4, 4, 10, 10, 1, 1, 1, 1, 41, 2, 41, 2, 6, 6,
879 1, 1, 11, 42, 11, 43, 3, 42, 3, 17, 4, 43, 1, 17, 7, 1,
880 8, 44, 4, 7, 44, 5, 8, 2, 5, 1, 2, 48, 45, 1, 12, 45,
881 12, 48, 13, 13, 1, 9, 9, 46, 1, 46, 47, 47, 49, 18, 18, 49},
884 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 1, -1, 3, -3, 1,
885 -1, -2, 2, 1, -1, 1, -1, 4, -4, -2, 2, 1, -1, 1, -1, 5,
886 -5, -3, 3, 2, -2, 1, 0, -1, 1, -1, 1, -1, 6, -6, 2, -2,
887 1, -1, 1, 1, -1, -1, -3, 3, 7, 2, -7, -2, -4, 4, 2, -2,
888 2, -2, 1, -1, 8, -8, 3, -3, 1, -1, -5, 5, 9, 1, -9, 1,
889 -1, -1, 1, -1, -4, 4, 1, -1, 3, -3, 1, -10, 10, 1, 2, -1,
890 -1, -2, 6, -6, 2, 11, -11, -2, 3, -3, 1, -4, 4, -1, 3, -3,
891 1, 3, 12, -3, -5, -12, -1, 5, 2, -2, 1, -1, -7, 1, 13, 7,
892 -1, -13, 2, -2, 4, -4, 1, 2, -2, -1, 1, 14, -14, 1, 1, 1,
893 -1, -5, -1, -1, 5, -1, -6, 2, -15, 15, 6, 1, -1, -8, 8, -2,
894 -4, 4, 1, 1, -1, -1, 16, 2, -16, -2, 2, -2, 4, 3, -4, -3,
895 -1, -4, 4, 1, -17, 17, -1, -9, 1, 1, 9, 1, -5, -1, -1, 5,
896 -7, 7, 6, -6, 3, -3, 18, -18, 19, -19, 1, -10, -1, 10, -5, 5,
897 20, -20, -3, 1, 3, 1, 8, -1, -8, 2, 7, -1, -21, -2, 5, 21,
898 5, -1, -7, -5, 1, -6, -5, -11, 6, 22, 11, 1, 1, -22, -3, -1,
899 3, -1, 3, -3, -23, 4, -4, 1, 23, -1, 1, -1, 1, -2, 2, -1}
905 {1, 1, 1, 1, 0, 2, 2, 1, 1, 3, 3, 0, 1, 1, 2, 2,
906 4, 4, 1, 1, 5, 5, 1, 1, 2, 2, 3, 3, 6, 6, 1, 1,
907 7, 7, 8, 1, 8, 2, 2, 1, 4, 4, 1, 3, 1, 3, 9, 9,
908 2, 2, 1, 5, 1, 5, 10, 10, 1, 1, 11, 11, 3, 6, 3, 4,
909 4, 6, 2, 2, 1, 12, 1, 12, 7, 13, 7, 13, 1, 1, 8, 8,
910 2, 2, 14, 14, 16, 15, 16, 5, 5, 1, 3, 15, 1, 3, 4, 4,
911 1, 1, 17, 17, 2, 2, 6, 6, 1, 18, 1, 18, 22, 21, 22, 21,
912 25, 24, 25, 19, 9, 20, 9, 23, 19, 24, 20, 3, 23, 7, 3, 1,
913 1, 7, 28, 26, 29, 5, 28, 26, 5, 8, 29, 4, 8, 27, 2, 2,
914 4, 27, 1, 1, 10, 36, 10, 33, 33, 36, 30, 1, 32, 32, 1, 30,
915 6, 31, 31, 35, 3, 6, 11, 11, 3, 2, 35, 2, 34, 1, 34, 1,
916 37, 37, 12, 7, 12, 5, 41, 5, 4, 7, 1, 8, 13, 4, 1, 41,
917 13, 38, 8, 38, 9, 1, 40, 40, 9, 1, 39, 2, 2, 49, 39, 42,
918 3, 3, 14, 16, 49, 14, 16, 42, 43, 43, 6, 6, 15, 1, 1, 15,
919 44, 44, 1, 1, 50, 48, 4, 5, 4, 7, 5, 2, 10, 10, 48, 7,
920 50, 45, 2, 1, 45, 8, 8, 1, 46, 46, 3, 47, 47, 3, 1, 1},
923 { 1, -1, 2, -2, 0, 1, -1, 3, -3, 1, -1, 0, 4, -4, 2, -2,
924 1, -1, 5, -5, 1, -1, 6, -6, 3, -3, 2, -2, 1, -1, 7, -7,
925 1, -1, 1, 8, -1, 4, -4, -8, 2, -2, 9, 3, -9, -3, 1, -1,
926 5, -5, 10, 2, -10, -2, 1, -1, 11, -11, 1, -1, -4, 2, 4, 3,
927 -3, -2, 6, -6, 12, 1, -12, -1, 2, 1, -2, -1, 13, -13, 2, -2,
928 7, -7, 1, -1, 1, 1, -1, 3, -3, 14, 5, -1, -14, -5, 4, -4,
929 15, -15, 1, -1, 8, -8, -3, 3, 16, 1, -16, -1, 1, 1, -1, -1,
930 1, 1, -1, 1, 2, 1, -2, 1, -1, -1, -1, 6, -1, 3, -6, 17,
931 -17, -3, 1, 1, 1, 4, -1, -1, -4, 3, -1, 5, -3, -1, -9, 9,
932 -5, 1, 18, -18, 2, 1, -2, 1, -1, -1, 1, 19, -1, 1, -19, -1,
933 4, 1, -1, 1, 7, -4, -2, 2, -7, 10, -1, -10, 1, 20, -1, -20,
934 1, -1, 2, 4, -2, 5, 1, -5, 6, -4, 21, 4, 2, -6, -21, -1,
935 -2, 1, -4, -1, -3, 22, -1, 1, 3, -22, -1, 11, -11, 1, 1, 1,
936 8, -8, 2, 2, -1, -2, -2, -1, 1, -1, -5, 5, 2, 23, -23, -2,
937 1, -1, 24, -24, -1, -1, 7, 6, -7, 5, -6, 12, -3, 3, 1, -5,
938 1, 1, -12, 25, -1, -5, 5, -25, -1, 1, 9, 1, -1, -9, 26, -26}