2 * common functions for Indeo Video Interactive codecs (Indeo4 and Indeo5)
4 * Copyright (c) 2009 Maxim Poliakovski
6 * This file is part of FFmpeg.
8 * FFmpeg is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
13 * FFmpeg is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with FFmpeg; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
25 * This file contains functions and data shared by both Indeo4 and
29 #define BITSTREAM_READER_LE
32 #include "ivi_common.h"
33 #include "libavutil/common.h"
36 extern const IVIHuffDesc ff_ivi_mb_huff_desc[8]; ///< static macroblock huffman tables
37 extern const IVIHuffDesc ff_ivi_blk_huff_desc[8]; ///< static block huffman tables
39 VLC ff_ivi_mb_vlc_tabs [8];
40 VLC ff_ivi_blk_vlc_tabs[8];
43 * Reverse "nbits" bits of the value "val" and return the result
44 * in the least significant bits.
46 static uint16_t inv_bits(uint16_t val, int nbits)
51 res = av_reverse[val] >> (8-nbits);
53 res = ((av_reverse[val & 0xFF] << 8) + (av_reverse[val >> 8])) >> (16-nbits);
58 int ff_ivi_create_huff_from_desc(const IVIHuffDesc *cb, VLC *vlc, int flag)
60 int pos, i, j, codes_per_row, prefix, not_last_row;
61 uint16_t codewords[256]; /* FIXME: move this temporal storage out? */
64 pos = 0; /* current position = 0 */
66 for (i = 0; i < cb->num_rows; i++) {
67 codes_per_row = 1 << cb->xbits[i];
68 not_last_row = (i != cb->num_rows - 1);
69 prefix = ((1 << i) - 1) << (cb->xbits[i] + not_last_row);
71 for (j = 0; j < codes_per_row; j++) {
72 if (pos >= 256) /* Some Indeo5 codebooks can have more than 256 */
73 break; /* elements, but only 256 codes are allowed! */
75 bits[pos] = i + cb->xbits[i] + not_last_row;
76 if (bits[pos] > IVI_VLC_BITS)
77 return -1; /* invalid descriptor */
79 codewords[pos] = inv_bits((prefix | j), bits[pos]);
87 /* number of codewords = pos */
88 return init_vlc(vlc, IVI_VLC_BITS, pos, bits, 1, 1, codewords, 2, 2,
89 (flag ? INIT_VLC_USE_NEW_STATIC : 0) | INIT_VLC_LE);
92 void ff_ivi_init_static_vlc(void)
95 static VLC_TYPE table_data[8192 * 16][2];
96 static int initialized_vlcs = 0;
100 for (i = 0; i < 8; i++) {
101 ff_ivi_mb_vlc_tabs[i].table = table_data + i * 2 * 8192;
102 ff_ivi_mb_vlc_tabs[i].table_allocated = 8192;
103 ff_ivi_create_huff_from_desc(&ff_ivi_mb_huff_desc[i], &ff_ivi_mb_vlc_tabs[i], 1);
104 ff_ivi_blk_vlc_tabs[i].table = table_data + (i * 2 + 1) * 8192;
105 ff_ivi_blk_vlc_tabs[i].table_allocated = 8192;
106 ff_ivi_create_huff_from_desc(&ff_ivi_blk_huff_desc[i], &ff_ivi_blk_vlc_tabs[i], 1);
108 initialized_vlcs = 1;
111 int ff_ivi_dec_huff_desc(GetBitContext *gb, int desc_coded, int which_tab,
112 IVIHuffTab *huff_tab, AVCodecContext *avctx)
115 IVIHuffDesc new_huff;
118 /* select default table */
119 huff_tab->tab = (which_tab) ? &ff_ivi_blk_vlc_tabs[7]
120 : &ff_ivi_mb_vlc_tabs [7];
122 huff_tab->tab_sel = get_bits(gb, 3);
123 if (huff_tab->tab_sel == 7) {
124 /* custom huffman table (explicitly encoded) */
125 new_huff.num_rows = get_bits(gb, 4);
127 for (i = 0; i < new_huff.num_rows; i++)
128 new_huff.xbits[i] = get_bits(gb, 4);
130 /* Have we got the same custom table? Rebuild if not. */
131 if (ff_ivi_huff_desc_cmp(&new_huff, &huff_tab->cust_desc) || !huff_tab->cust_tab.table) {
132 ff_ivi_huff_desc_copy(&huff_tab->cust_desc, &new_huff);
134 if (huff_tab->cust_tab.table)
135 ff_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 av_cold int 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 band->bufsize = buf_size/2;
213 if (!band->bufs[0] || !band->bufs[1])
214 return AVERROR(ENOMEM);
216 /* allocate the 3rd band buffer for scalability mode */
217 if (cfg->luma_bands > 1) {
218 band->bufs[2] = av_malloc(buf_size);
220 return AVERROR(ENOMEM);
223 planes[p].bands[0].blk_vlc.cust_desc.num_rows = 0; /* reset custom vlc */
230 av_cold void ff_ivi_free_buffers(IVIPlaneDesc *planes)
234 for (p = 0; p < 3; p++) {
235 for (b = 0; b < planes[p].num_bands; b++) {
236 av_freep(&planes[p].bands[b].bufs[0]);
237 av_freep(&planes[p].bands[b].bufs[1]);
238 av_freep(&planes[p].bands[b].bufs[2]);
240 if (planes[p].bands[b].blk_vlc.cust_tab.table)
241 ff_free_vlc(&planes[p].bands[b].blk_vlc.cust_tab);
242 for (t = 0; t < planes[p].bands[b].num_tiles; t++)
243 av_freep(&planes[p].bands[b].tiles[t].mbs);
244 av_freep(&planes[p].bands[b].tiles);
246 av_freep(&planes[p].bands);
250 av_cold int ff_ivi_init_tiles(IVIPlaneDesc *planes, int tile_width, int tile_height)
252 int p, b, x, y, x_tiles, y_tiles, t_width, t_height;
254 IVITile *tile, *ref_tile;
256 for (p = 0; p < 3; p++) {
257 t_width = !p ? tile_width : (tile_width + 3) >> 2;
258 t_height = !p ? tile_height : (tile_height + 3) >> 2;
260 if (!p && planes[0].num_bands == 4) {
264 if(t_width<=0 || t_height<=0)
265 return AVERROR(EINVAL);
267 for (b = 0; b < planes[p].num_bands; b++) {
268 band = &planes[p].bands[b];
269 x_tiles = IVI_NUM_TILES(band->width, t_width);
270 y_tiles = IVI_NUM_TILES(band->height, t_height);
271 band->num_tiles = x_tiles * y_tiles;
273 av_freep(&band->tiles);
274 band->tiles = av_mallocz(band->num_tiles * sizeof(IVITile));
276 return AVERROR(ENOMEM);
280 /* use the first luma band as reference for motion vectors
282 ref_tile = planes[0].bands[0].tiles;
284 for (y = 0; y < band->height; y += t_height) {
285 for (x = 0; x < band->width; x += t_width) {
288 tile->width = FFMIN(band->width - x, t_width);
289 tile->height = FFMIN(band->height - y, t_height);
290 tile->is_empty = tile->data_size = 0;
291 /* calculate number of macroblocks */
292 tile->num_MBs = IVI_MBs_PER_TILE(tile->width, tile->height,
295 av_freep(&tile->mbs);
296 tile->mbs = av_malloc(tile->num_MBs * sizeof(IVIMbInfo));
298 return AVERROR(ENOMEM);
302 tile->ref_mbs = ref_tile->mbs;
316 int ff_ivi_dec_tile_data_size(GetBitContext *gb)
322 len = get_bits(gb, 8);
324 len = get_bits_long(gb, 24);
327 /* align the bitstream reader on the byte boundary */
333 int ff_ivi_decode_blocks(GetBitContext *gb, IVIBandDesc *band, IVITile *tile)
335 int mbn, blk, num_blocks, num_coeffs, blk_size, scan_pos, run, val,
336 pos, is_intra, mc_type, mv_x, mv_y, col_mask;
337 uint8_t col_flags[8];
338 int32_t prev_dc, trvec[64];
339 uint32_t cbp, sym, lo, hi, quant, buf_offs, q;
341 RVMapDesc *rvmap = band->rv_map;
342 void (*mc_with_delta_func)(int16_t *buf, const int16_t *ref_buf, uint32_t pitch, int mc_type);
343 void (*mc_no_delta_func) (int16_t *buf, const int16_t *ref_buf, uint32_t pitch, int mc_type);
344 const uint16_t *base_tab;
345 const uint8_t *scale_tab;
347 prev_dc = 0; /* init intra prediction for the DC coefficient */
349 blk_size = band->blk_size;
350 col_mask = blk_size - 1; /* column mask for tracking non-zero coeffs */
351 num_blocks = (band->mb_size != blk_size) ? 4 : 1; /* number of blocks per mb */
352 num_coeffs = blk_size * blk_size;
354 mc_with_delta_func = ff_ivi_mc_8x8_delta;
355 mc_no_delta_func = ff_ivi_mc_8x8_no_delta;
357 mc_with_delta_func = ff_ivi_mc_4x4_delta;
358 mc_no_delta_func = ff_ivi_mc_4x4_no_delta;
361 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
362 is_intra = !mb->type;
364 buf_offs = mb->buf_offs;
366 quant = av_clip(band->glob_quant + mb->q_delta, 0, 23);
368 base_tab = is_intra ? band->intra_base : band->inter_base;
369 scale_tab = is_intra ? band->intra_scale : band->inter_scale;
371 quant = scale_tab[quant];
376 if (!band->is_halfpel) {
377 mc_type = 0; /* we have only fullpel vectors */
379 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
381 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
385 for (blk = 0; blk < num_blocks; blk++) {
386 /* adjust block position in the buffer according to its number */
388 buf_offs += blk_size;
389 } else if (blk == 2) {
390 buf_offs -= blk_size;
391 buf_offs += blk_size * band->pitch;
394 if (cbp & 1) { /* block coded ? */
396 memset(trvec, 0, num_coeffs*sizeof(trvec[0])); /* zero transform vector */
397 memset(col_flags, 0, sizeof(col_flags)); /* zero column flags */
399 while (scan_pos <= num_coeffs) {
400 sym = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
401 if (sym == rvmap->eob_sym)
402 break; /* End of block */
404 if (sym == rvmap->esc_sym) { /* Escape - run/val explicitly coded using 3 vlc codes */
405 run = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1) + 1;
406 lo = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
407 hi = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
408 val = IVI_TOSIGNED((hi << 6) | lo); /* merge them and convert into signed val */
411 av_log(NULL, AV_LOG_ERROR, "Invalid sym encountered: %d.\n", sym);
414 run = rvmap->runtab[sym];
415 val = rvmap->valtab[sym];
418 /* de-zigzag and dequantize */
420 if (scan_pos >= (unsigned)num_coeffs)
422 pos = band->scan[scan_pos];
425 av_dlog(NULL, "Val = 0 encountered!\n");
427 q = (base_tab[pos] * quant) >> 9;
429 val = val * q + FFSIGN(val) * (((q ^ 1) - 1) >> 1);
431 col_flags[pos & col_mask] |= !!val; /* track columns containing non-zero coeffs */
434 if (scan_pos >= num_coeffs && sym != rvmap->eob_sym)
435 return -1; /* corrupt block data */
437 /* undoing DC coeff prediction for intra-blocks */
438 if (is_intra && band->is_2d_trans) {
441 col_flags[0] |= !!prev_dc;
443 if(band->transform_size > band->blk_size){
444 av_log(0, AV_LOG_ERROR, "Too large transform\n");
445 return AVERROR_INVALIDDATA;
447 /* apply inverse transform */
448 band->inv_transform(trvec, band->buf + buf_offs,
449 band->pitch, col_flags);
451 /* apply motion compensation */
453 mc_with_delta_func(band->buf + buf_offs,
454 band->ref_buf + buf_offs + mv_y * band->pitch + mv_x,
455 band->pitch, mc_type);
457 /* block not coded */
458 /* for intra blocks apply the dc slant transform */
459 /* for inter - perform the motion compensation without delta */
460 if (is_intra && band->dc_transform) {
461 band->dc_transform(&prev_dc, band->buf + buf_offs,
462 band->pitch, blk_size);
464 mc_no_delta_func(band->buf + buf_offs,
465 band->ref_buf + buf_offs + mv_y * band->pitch + mv_x,
466 band->pitch, mc_type);
478 void ff_ivi_process_empty_tile(AVCodecContext *avctx, IVIBandDesc *band,
479 IVITile *tile, int32_t mv_scale)
481 int x, y, need_mc, mbn, blk, num_blocks, mv_x, mv_y, mc_type;
482 int offs, mb_offset, row_offset;
483 IVIMbInfo *mb, *ref_mb;
486 void (*mc_no_delta_func)(int16_t *buf, const int16_t *ref_buf, uint32_t pitch,
489 if( tile->num_MBs != IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size) ){
490 av_log(avctx, AV_LOG_ERROR, "allocated tile size %d mismatches parameters %d in ff_ivi_process_empty_tile()\n",
491 tile->num_MBs, IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size));
495 offs = tile->ypos * band->pitch + tile->xpos;
497 ref_mb = tile->ref_mbs;
498 row_offset = band->mb_size * band->pitch;
499 need_mc = 0; /* reset the mc tracking flag */
501 for (y = tile->ypos; y < (tile->ypos + tile->height); y += band->mb_size) {
504 for (x = tile->xpos; x < (tile->xpos + tile->width); x += band->mb_size) {
507 mb->buf_offs = mb_offset;
509 mb->type = 1; /* set the macroblocks type = INTER */
510 mb->cbp = 0; /* all blocks are empty */
512 if (!band->qdelta_present && !band->plane && !band->band_num) {
513 mb->q_delta = band->glob_quant;
518 if (band->inherit_qdelta && ref_mb)
519 mb->q_delta = ref_mb->q_delta;
521 if (band->inherit_mv && ref_mb) {
522 /* motion vector inheritance */
524 mb->mv_x = ivi_scale_mv(ref_mb->mv_x, mv_scale);
525 mb->mv_y = ivi_scale_mv(ref_mb->mv_y, mv_scale);
527 mb->mv_x = ref_mb->mv_x;
528 mb->mv_y = ref_mb->mv_y;
530 need_mc |= mb->mv_x || mb->mv_y; /* tracking non-zero motion vectors */
536 mb_offset += band->mb_size;
541 if (band->inherit_mv && need_mc) { /* apply motion compensation if there is at least one non-zero motion vector */
542 num_blocks = (band->mb_size != band->blk_size) ? 4 : 1; /* number of blocks per mb */
543 mc_no_delta_func = (band->blk_size == 8) ? ff_ivi_mc_8x8_no_delta
544 : ff_ivi_mc_4x4_no_delta;
546 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
549 if (!band->is_halfpel) {
550 mc_type = 0; /* we have only fullpel vectors */
552 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
554 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
557 for (blk = 0; blk < num_blocks; blk++) {
558 /* adjust block position in the buffer according with its number */
559 offs = mb->buf_offs + band->blk_size * ((blk & 1) + !!(blk & 2) * band->pitch);
560 mc_no_delta_func(band->buf + offs,
561 band->ref_buf + offs + mv_y * band->pitch + mv_x,
562 band->pitch, mc_type);
566 /* copy data from the reference tile into the current one */
567 src = band->ref_buf + tile->ypos * band->pitch + tile->xpos;
568 dst = band->buf + tile->ypos * band->pitch + tile->xpos;
569 for (y = 0; y < tile->height; y++) {
570 memcpy(dst, src, tile->width*sizeof(band->buf[0]));
579 uint16_t ivi_calc_band_checksum (IVIBandDesc *band)
582 int16_t *src, checksum;
587 for (y = 0; y < band->height; src += band->pitch, y++)
588 for (x = 0; x < band->width; x++)
594 int ivi_check_band (IVIBandDesc *band, const uint8_t *ref, int pitch)
603 for (y = 0; y < band->height; src += band->pitch, y++) {
604 for (x = 0; x < band->width; x++) {
605 t1 = av_clip(src[x] + 128, 0, 255);
608 av_log(NULL, AV_LOG_ERROR, "Data mismatch: row %d, column %d\n",
609 y / band->blk_size, x / band->blk_size);
620 void ff_ivi_output_plane(IVIPlaneDesc *plane, uint8_t *dst, int dst_pitch)
623 const int16_t *src = plane->bands[0].buf;
624 uint32_t pitch = plane->bands[0].pitch;
629 for (y = 0; y < plane->height; y++) {
630 for (x = 0; x < plane->width; x++)
631 dst[x] = av_clip_uint8(src[x] + 128);
639 * These are 2x8 predefined Huffman codebooks for coding macroblock/block
640 * signals. They are specified using "huffman descriptors" in order to
641 * avoid huge static tables. The decoding tables will be generated at
642 * startup from these descriptors.
644 const IVIHuffDesc ff_ivi_mb_huff_desc[8] = {
645 {8, {0, 4, 5, 4, 4, 4, 6, 6}},
646 {12, {0, 2, 2, 3, 3, 3, 3, 5, 3, 2, 2, 2}},
647 {12, {0, 2, 3, 4, 3, 3, 3, 3, 4, 3, 2, 2}},
648 {12, {0, 3, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2}},
649 {13, {0, 4, 4, 3, 3, 3, 3, 2, 3, 3, 2, 1, 1}},
650 {9, {0, 4, 4, 4, 4, 3, 3, 3, 2}},
651 {10, {0, 4, 4, 4, 4, 3, 3, 2, 2, 2}},
652 {12, {0, 4, 4, 4, 3, 3, 2, 3, 2, 2, 2, 2}}
655 const IVIHuffDesc ff_ivi_blk_huff_desc[8] = {
656 {10, {1, 2, 3, 4, 4, 7, 5, 5, 4, 1}},
657 {11, {2, 3, 4, 4, 4, 7, 5, 4, 3, 3, 2}},
658 {12, {2, 4, 5, 5, 5, 5, 6, 4, 4, 3, 1, 1}},
659 {13, {3, 3, 4, 4, 5, 6, 6, 4, 4, 3, 2, 1, 1}},
660 {11, {3, 4, 4, 5, 5, 5, 6, 5, 4, 2, 2}},
661 {13, {3, 4, 5, 5, 5, 5, 6, 4, 3, 3, 2, 1, 1}},
662 {13, {3, 4, 5, 5, 5, 6, 5, 4, 3, 3, 2, 1, 1}},
663 {9, {3, 4, 4, 5, 5, 5, 6, 5, 5}}
668 * Scan patterns shared between indeo4 and indeo5
670 const uint8_t ff_ivi_vertical_scan_8x8[64] = {
671 0, 8, 16, 24, 32, 40, 48, 56,
672 1, 9, 17, 25, 33, 41, 49, 57,
673 2, 10, 18, 26, 34, 42, 50, 58,
674 3, 11, 19, 27, 35, 43, 51, 59,
675 4, 12, 20, 28, 36, 44, 52, 60,
676 5, 13, 21, 29, 37, 45, 53, 61,
677 6, 14, 22, 30, 38, 46, 54, 62,
678 7, 15, 23, 31, 39, 47, 55, 63
681 const uint8_t ff_ivi_horizontal_scan_8x8[64] = {
682 0, 1, 2, 3, 4, 5, 6, 7,
683 8, 9, 10, 11, 12, 13, 14, 15,
684 16, 17, 18, 19, 20, 21, 22, 23,
685 24, 25, 26, 27, 28, 29, 30, 31,
686 32, 33, 34, 35, 36, 37, 38, 39,
687 40, 41, 42, 43, 44, 45, 46, 47,
688 48, 49, 50, 51, 52, 53, 54, 55,
689 56, 57, 58, 59, 60, 61, 62, 63
692 const uint8_t ff_ivi_direct_scan_4x4[16] = {
693 0, 1, 4, 8, 5, 2, 3, 6, 9, 12, 13, 10, 7, 11, 14, 15
698 * Run-value (RLE) tables.
700 const RVMapDesc ff_ivi_rvmap_tabs[9] = {
705 {1, 1, 0, 1, 1, 0, 1, 1, 2, 2, 1, 1, 1, 1, 3, 3,
706 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 1, 1, 2, 2, 5, 5,
707 1, 1, 3, 3, 1, 1, 6, 6, 1, 2, 1, 2, 7, 7, 1, 1,
708 8, 8, 1, 1, 4, 2, 1, 4, 2, 1, 3, 3, 1, 1, 1, 9,
709 9, 1, 2, 1, 2, 1, 5, 5, 1, 1, 10, 10, 1, 1, 3, 3,
710 2, 2, 1, 1, 11, 11, 6, 4, 4, 1, 6, 1, 2, 1, 2, 12,
711 8, 1, 12, 7, 8, 7, 1, 16, 1, 16, 1, 3, 3, 13, 1, 13,
712 2, 2, 1, 15, 1, 5, 14, 15, 1, 5, 14, 1, 17, 8, 17, 8,
713 1, 4, 4, 2, 2, 1, 25, 25, 24, 24, 1, 3, 1, 3, 1, 8,
714 6, 7, 6, 1, 18, 8, 18, 1, 7, 23, 2, 2, 23, 1, 1, 21,
715 22, 9, 9, 22, 19, 1, 21, 5, 19, 5, 1, 33, 20, 33, 20, 8,
716 4, 4, 1, 32, 2, 2, 8, 3, 32, 26, 3, 1, 7, 7, 26, 6,
717 1, 6, 1, 1, 16, 1, 10, 1, 10, 2, 16, 29, 28, 2, 29, 28,
718 1, 27, 5, 8, 5, 27, 1, 8, 3, 7, 3, 31, 41, 31, 1, 41,
719 6, 1, 6, 7, 4, 4, 1, 1, 2, 1, 2, 11, 34, 30, 11, 1,
720 30, 15, 15, 34, 36, 40, 36, 40, 35, 35, 37, 37, 39, 39, 38, 38},
723 { 1, -1, 0, 2, -2, 0, 3, -3, 1, -1, 4, -4, 5, -5, 1, -1,
724 6, -6, 2, -2, 7, -7, 1, -1, 8, -8, 9, -9, 3, -3, 1, -1,
725 10, -10, 2, -2, 11, -11, 1, -1, 12, 4, -12, -4, 1, -1, 13, -13,
726 1, -1, 14, -14, 2, 5, 15, -2, -5, -15, -3, 3, 16, -16, 17, 1,
727 -1, -17, 6, 18, -6, -18, 2, -2, 19, -19, 1, -1, 20, -20, 4, -4,
728 7, -7, 21, -21, 1, -1, 2, 3, -3, 22, -2, -22, 8, 23, -8, 1,
729 2, -23, -1, 2, -2, -2, 24, 1, -24, -1, 25, 5, -5, 1, -25, -1,
730 9, -9, 26, 1, -26, 3, 1, -1, 27, -3, -1, -27, 1, 3, -1, -3,
731 28, -4, 4, 10, -10, -28, 1, -1, 1, -1, 29, 6, -29, -6, 30, -4,
732 3, 3, -3, -30, 1, 4, -1, 31, -3, 1, 11, -11, -1, -31, 32, -1,
733 -1, 2, -2, 1, 1, -32, 1, 4, -1, -4, 33, -1, 1, 1, -1, 5,
734 5, -5, -33, -1, -12, 12, -5, -7, 1, 1, 7, 34, 4, -4, -1, 4,
735 -34, -4, 35, 36, -2, -35, -2, -36, 2, 13, 2, -1, 1, -13, 1, -1,
736 37, 1, -5, 6, 5, -1, 38, -6, -8, 5, 8, -1, 1, 1, -37, -1,
737 5, 39, -5, -5, 6, -6, -38, -39, -14, 40, 14, 2, 1, 1, -2, -40,
738 -1, -2, 2, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1}
744 {0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 8, 6, 8, 7,
745 7, 9, 9, 10, 10, 11, 11, 1, 12, 1, 12, 13, 13, 16, 14, 16,
746 14, 15, 15, 17, 17, 18, 0, 18, 19, 20, 21, 19, 22, 21, 20, 22,
747 25, 24, 2, 25, 24, 23, 23, 2, 26, 28, 26, 28, 29, 27, 29, 27,
748 33, 33, 1, 32, 1, 3, 32, 30, 36, 3, 36, 30, 31, 31, 35, 34,
749 37, 41, 34, 35, 37, 4, 41, 4, 49, 8, 8, 49, 40, 38, 5, 38,
750 40, 39, 5, 39, 42, 43, 42, 7, 57, 6, 43, 44, 6, 50, 7, 44,
751 57, 48, 50, 48, 45, 45, 46, 47, 51, 46, 47, 58, 1, 51, 58, 1,
752 52, 59, 53, 9, 52, 55, 55, 59, 53, 56, 54, 56, 54, 9, 64, 64,
753 60, 63, 60, 63, 61, 62, 61, 62, 2, 10, 2, 10, 11, 1, 11, 13,
754 12, 1, 12, 13, 16, 16, 8, 8, 14, 3, 3, 15, 14, 15, 4, 4,
755 1, 17, 17, 5, 1, 7, 7, 5, 6, 1, 2, 2, 6, 22, 1, 25,
756 21, 22, 8, 24, 1, 21, 25, 24, 8, 18, 18, 23, 9, 20, 23, 33,
757 29, 33, 20, 1, 19, 1, 29, 36, 9, 36, 19, 41, 28, 57, 32, 3,
758 28, 3, 1, 27, 49, 49, 1, 32, 26, 26, 2, 4, 4, 7, 57, 41,
759 2, 7, 10, 5, 37, 16, 10, 27, 8, 8, 13, 16, 37, 13, 1, 5},
762 {0, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1,
763 -1, 1, -1, 1, -1, 1, -1, 2, 1, -2, -1, 1, -1, 1, 1, -1,
764 -1, 1, -1, 1, -1, 1, 0, -1, 1, 1, 1, -1, 1, -1, -1, -1,
765 1, 1, 2, -1, -1, 1, -1, -2, 1, 1, -1, -1, 1, 1, -1, -1,
766 1, -1, 3, 1, -3, 2, -1, 1, 1, -2, -1, -1, -1, 1, 1, 1,
767 1, 1, -1, -1, -1, 2, -1, -2, 1, 2, -2, -1, 1, 1, 2, -1,
768 -1, 1, -2, -1, 1, 1, -1, 2, 1, 2, -1, 1, -2, -1, -2, -1,
769 -1, 1, 1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 4, -1, -1, -4,
770 1, 1, 1, 2, -1, -1, 1, -1, -1, 1, -1, -1, 1, -2, 1, -1,
771 1, 1, -1, -1, 1, 1, -1, -1, 3, 2, -3, -2, 2, 5, -2, 2,
772 2, -5, -2, -2, -2, 2, -3, 3, 2, 3, -3, 2, -2, -2, 3, -3,
773 6, 2, -2, 3, -6, 3, -3, -3, 3, 7, -4, 4, -3, 2, -7, 2,
774 2, -2, -4, 2, 8, -2, -2, -2, 4, 2, -2, 2, 3, 2, -2, -2,
775 2, 2, -2, -8, -2, 9, -2, 2, -3, -2, 2, -2, 2, 2, 2, 4,
776 -2, -4, 10, 2, 2, -2, -9, -2, 2, -2, 5, 4, -4, 4, -2, 2,
777 -5, -4, -3, 4, 2, -3, 3, -2, -5, 5, 3, 3, -2, -3, -10, -4}
783 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 0, 1, 1, 5, 5,
784 2, 2, 6, 6, 7, 7, 1, 8, 1, 8, 3, 3, 9, 9, 1, 2,
785 2, 1, 4, 10, 4, 10, 11, 11, 1, 5, 12, 12, 1, 5, 13, 13,
786 3, 3, 6, 6, 2, 2, 14, 14, 16, 16, 15, 7, 15, 8, 8, 7,
787 1, 1, 17, 17, 4, 4, 1, 1, 18, 18, 2, 2, 5, 5, 25, 3,
788 9, 3, 25, 9, 19, 24, 19, 24, 1, 21, 20, 1, 21, 22, 20, 22,
789 23, 23, 8, 6, 33, 6, 8, 33, 7, 7, 26, 26, 1, 32, 1, 32,
790 28, 4, 28, 10, 29, 27, 27, 10, 41, 4, 29, 2, 2, 41, 36, 31,
791 49, 31, 34, 30, 34, 36, 30, 35, 1, 49, 11, 5, 35, 11, 1, 3,
792 3, 5, 37, 37, 8, 40, 8, 40, 12, 12, 42, 42, 1, 38, 16, 57,
793 1, 6, 16, 39, 38, 6, 7, 7, 13, 13, 39, 43, 2, 43, 57, 2,
794 50, 9, 44, 9, 50, 4, 15, 48, 44, 4, 1, 15, 48, 14, 14, 1,
795 45, 45, 8, 3, 5, 8, 51, 47, 3, 46, 46, 47, 5, 51, 1, 17,
796 17, 58, 1, 58, 2, 52, 52, 2, 53, 7, 59, 6, 6, 56, 53, 55,
797 7, 55, 1, 54, 59, 56, 54, 10, 1, 10, 4, 60, 1, 60, 8, 4,
798 8, 64, 64, 61, 1, 63, 3, 63, 62, 61, 5, 11, 5, 3, 11, 62},
801 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 0, 3, -3, 1, -1,
802 2, -2, 1, -1, 1, -1, 4, 1, -4, -1, 2, -2, 1, -1, 5, 3,
803 -3, -5, 2, 1, -2, -1, 1, -1, 6, 2, 1, -1, -6, -2, 1, -1,
804 3, -3, 2, -2, 4, -4, 1, -1, 1, -1, 1, 2, -1, 2, -2, -2,
805 7, -7, 1, -1, 3, -3, 8, -8, 1, -1, 5, -5, 3, -3, 1, 4,
806 2, -4, -1, -2, 1, 1, -1, -1, 9, 1, 1, -9, -1, 1, -1, -1,
807 1, -1, 3, -3, 1, 3, -3, -1, 3, -3, 1, -1, 10, 1, -10, -1,
808 1, 4, -1, 2, 1, -1, 1, -2, 1, -4, -1, 6, -6, -1, 1, 1,
809 1, -1, 1, 1, -1, -1, -1, 1, 11, -1, -2, 4, -1, 2, -11, 5,
810 -5, -4, -1, 1, 4, 1, -4, -1, -2, 2, 1, -1, 12, 1, -2, 1,
811 -12, 4, 2, 1, -1, -4, 4, -4, 2, -2, -1, 1, 7, -1, -1, -7,
812 -1, -3, 1, 3, 1, 5, 2, 1, -1, -5, 13, -2, -1, 2, -2, -13,
813 1, -1, 5, 6, 5, -5, 1, 1, -6, 1, -1, -1, -5, -1, 14, 2,
814 -2, 1, -14, -1, 8, 1, -1, -8, 1, 5, 1, 5, -5, 1, -1, 1,
815 -5, -1, 15, 1, -1, -1, -1, 3, -15, -3, 6, 1, 16, -1, 6, -6,
816 -6, 1, -1, 1, -16, 1, 7, -1, 1, -1, -6, -3, 6, -7, 3, -1}
822 {0, 1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6, 6, 7,
823 7, 8, 8, 9, 9, 2, 2, 10, 10, 1, 1, 11, 11, 12, 12, 3,
824 3, 13, 13, 0, 14, 14, 16, 15, 16, 15, 4, 4, 17, 1, 17, 1,
825 5, 5, 18, 18, 2, 2, 6, 6, 8, 19, 7, 8, 7, 19, 20, 20,
826 21, 21, 22, 24, 22, 24, 23, 23, 1, 1, 25, 25, 3, 3, 26, 26,
827 9, 9, 27, 27, 28, 28, 33, 29, 4, 33, 29, 1, 4, 1, 32, 32,
828 2, 2, 31, 10, 30, 10, 30, 31, 34, 34, 5, 5, 36, 36, 35, 41,
829 35, 11, 41, 11, 37, 1, 8, 8, 37, 6, 1, 6, 40, 7, 7, 40,
830 12, 38, 12, 39, 39, 38, 49, 13, 49, 13, 3, 42, 3, 42, 16, 16,
831 43, 43, 14, 14, 1, 1, 44, 15, 44, 15, 2, 2, 57, 48, 50, 48,
832 57, 50, 4, 45, 45, 4, 46, 47, 47, 46, 1, 51, 1, 17, 17, 51,
833 8, 9, 9, 5, 58, 8, 58, 5, 52, 52, 55, 56, 53, 56, 55, 59,
834 59, 53, 54, 1, 6, 54, 7, 7, 6, 1, 2, 3, 2, 3, 64, 60,
835 60, 10, 10, 64, 61, 62, 61, 63, 1, 63, 62, 1, 18, 24, 18, 4,
836 25, 4, 8, 21, 21, 1, 24, 22, 25, 22, 8, 11, 19, 11, 23, 1,
837 20, 23, 19, 20, 5, 12, 5, 1, 16, 2, 12, 13, 2, 13, 1, 16},
840 { 0, 1, -1, 1, -1, 1, -1, 1, -1, 2, -2, 1, -1, 1, -1, 1,
841 -1, 1, -1, 1, -1, 2, -2, 1, -1, 3, -3, 1, -1, 1, -1, 2,
842 -2, 1, -1, 0, 1, -1, 1, 1, -1, -1, 2, -2, 1, 4, -1, -4,
843 2, -2, 1, -1, -3, 3, 2, -2, 2, 1, 2, -2, -2, -1, 1, -1,
844 1, -1, 1, 1, -1, -1, 1, -1, 5, -5, 1, -1, 3, -3, 1, -1,
845 2, -2, 1, -1, 1, -1, 1, 1, 3, -1, -1, 6, -3, -6, -1, 1,
846 4, -4, 1, 2, 1, -2, -1, -1, 1, -1, 3, -3, 1, -1, 1, 1,
847 -1, 2, -1, -2, 1, 7, -3, 3, -1, 3, -7, -3, 1, -3, 3, -1,
848 2, 1, -2, 1, -1, -1, 1, 2, -1, -2, -4, -1, 4, 1, 2, -2,
849 1, -1, -2, 2, 8, -8, -1, 2, 1, -2, -5, 5, 1, -1, -1, 1,
850 -1, 1, 4, -1, 1, -4, -1, -1, 1, 1, 9, 1, -9, 2, -2, -1,
851 -4, 3, -3, -4, -1, 4, 1, 4, 1, -1, 1, -1, 1, 1, -1, 1,
852 -1, -1, -1, 10, 4, 1, 4, -4, -4, -10, 6, 5, -6, -5, 1, -1,
853 1, 3, -3, -1, 1, -1, -1, -1, 11, 1, 1, -11, -2, -2, 2, 5,
854 -2, -5, -5, 2, -2, 12, 2, -2, 2, 2, 5, -3, -2, 3, -2, -12,
855 -2, 2, 2, 2, -5, 3, 5, 13, -3, 7, -3, -3, -7, 3, -13, 3}
861 {0, 1, 1, 1, 2, 2, 1, 3, 3, 1, 1, 1, 4, 4, 1, 5,
862 2, 1, 5, 2, 1, 1, 6, 6, 1, 1, 1, 1, 1, 7, 3, 1,
863 2, 3, 0, 1, 2, 7, 1, 1, 1, 8, 1, 1, 8, 1, 1, 1,
864 9, 1, 9, 1, 2, 1, 1, 2, 1, 1, 10, 4, 1, 10, 1, 4,
865 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 2, 1, 5, 1, 1, 1,
866 2, 5, 1, 11, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
867 2, 1, 6, 1, 6, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 12,
868 3, 1, 12, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1,
869 4, 1, 1, 1, 2, 1, 1, 4, 1, 1, 1, 1, 1, 1, 2, 1,
870 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 5,
871 1, 1, 1, 1, 1, 7, 1, 7, 1, 1, 2, 3, 1, 1, 1, 1,
872 5, 1, 1, 1, 1, 1, 1, 2, 13, 1, 1, 1, 1, 1, 1, 1,
873 1, 1, 1, 1, 1, 1, 1, 1, 13, 2, 1, 1, 4, 1, 1, 1,
874 3, 1, 6, 1, 1, 1, 14, 1, 1, 1, 1, 1, 14, 6, 1, 1,
875 1, 1, 15, 2, 4, 1, 2, 3, 15, 1, 1, 1, 8, 1, 1, 8,
876 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1},
879 { 0, 1, -1, 2, 1, -1, -2, 1, -1, 3, -3, 4, 1, -1, -4, 1,
880 2, 5, -1, -2, -5, 6, 1, -1, -6, 7, -7, 8, -8, 1, 2, 9,
881 3, -2, 0, -9, -3, -1, 10, -10, 11, 1, -11, 12, -1, -12, 13, -13,
882 1, 14, -1, -14, 4, 15, -15, -4, 16, -16, 1, 2, 17, -1, -17, -2,
883 18, -18, 19, -19, 20, 3, -20, 21, -21, -3, 5, 22, 2, -22, -23, 23,
884 -5, -2, 24, 1, -24, -1, 25, -25, 26, -26, -27, 27, 28, 29, -28, -29,
885 6, 30, 2, -31, -2, -30, 31, -6, -32, 32, 33, -33, 34, -35, -34, 1,
886 4, -36, -1, 35, 37, 36, 7, -37, 38, -4, -38, 39, 41, 40, -40, -39,
887 3, 42, -43, -41, -7, -42, 43, -3, 44, -44, 45, -45, 46, 47, 8, -47,
888 -48, -46, 50, -50, 48, 49, 51, -49, 52, -52, 5, -51, -8, -53, 53, 3,
889 -56, 56, 55, 54, -54, 2, 60, -2, -55, 58, 9, -5, 59, 57, -57, -63,
890 -3, -58, -60, -61, 61, -59, -62, -9, 1, 64, 62, 69, -64, 63, 65, -67,
891 -68, 66, -65, 68, -66, -69, 67, -70, -1, 10, 71, -71, 4, 73, 72, 70,
892 6, -76, -3, 74, -78, -74, 1, 78, 80, -72, -75, 76, -1, 3, -73, 79,
893 75, 77, 1, 11, -4, -79, -10, -6, -1, -77, -83, -80, 2, 81, -84, -2,
894 83, -81, 82, -82, 84, -87, -86, 85, -11, -85, 86, -89, 87, -88, 88, 89}
900 {1, 1, 0, 2, 1, 2, 1, 3, 3, 1, 1, 4, 4, 2, 2, 1,
901 1, 5, 5, 6, 1, 6, 1, 7, 7, 3, 3, 2, 8, 2, 8, 1,
902 1, 0, 9, 9, 1, 1, 10, 4, 10, 4, 11, 11, 2, 1, 2, 1,
903 12, 12, 3, 3, 1, 1, 13, 5, 5, 13, 14, 1, 1, 14, 2, 2,
904 6, 6, 15, 1, 1, 15, 16, 4, 7, 16, 4, 7, 1, 1, 3, 3,
905 8, 8, 2, 2, 1, 1, 17, 17, 1, 1, 18, 18, 5, 5, 2, 2,
906 1, 1, 9, 19, 9, 19, 20, 3, 3, 20, 1, 10, 21, 1, 10, 4,
907 4, 21, 22, 6, 6, 22, 1, 1, 23, 24, 2, 2, 23, 24, 11, 1,
908 1, 11, 7, 25, 7, 1, 1, 25, 8, 8, 3, 26, 3, 1, 12, 2,
909 2, 26, 1, 12, 5, 5, 27, 4, 1, 4, 1, 27, 28, 1, 28, 13,
910 1, 13, 2, 29, 2, 1, 32, 6, 1, 30, 14, 29, 14, 6, 3, 31,
911 3, 1, 30, 1, 32, 31, 33, 9, 33, 1, 1, 7, 9, 7, 2, 2,
912 1, 1, 4, 36, 34, 4, 5, 10, 10, 5, 34, 1, 1, 35, 8, 8,
913 36, 3, 35, 1, 15, 3, 2, 1, 16, 15, 16, 2, 37, 1, 37, 1,
914 1, 1, 6, 6, 38, 1, 38, 11, 1, 39, 39, 40, 11, 2, 41, 4,
915 40, 1, 2, 4, 1, 1, 1, 41, 3, 1, 3, 1, 5, 7, 5, 7},
918 { 1, -1, 0, 1, 2, -1, -2, 1, -1, 3, -3, 1, -1, 2, -2, 4,
919 -4, 1, -1, 1, 5, -1, -5, 1, -1, 2, -2, 3, 1, -3, -1, 6,
920 -6, 0, 1, -1, 7, -7, 1, 2, -1, -2, 1, -1, 4, 8, -4, -8,
921 1, -1, 3, -3, 9, -9, 1, 2, -2, -1, 1, 10, -10, -1, 5, -5,
922 2, -2, 1, 11, -11, -1, 1, 3, 2, -1, -3, -2, 12, -12, 4, -4,
923 2, -2, -6, 6, 13, -13, 1, -1, 14, -14, 1, -1, 3, -3, 7, -7,
924 15, -15, 2, 1, -2, -1, 1, 5, -5, -1, -16, 2, 1, 16, -2, 4,
925 -4, -1, 1, 3, -3, -1, 17, -17, 1, 1, -8, 8, -1, -1, 2, 18,
926 -18, -2, 3, 1, -3, 19, -19, -1, 3, -3, 6, 1, -6, 20, 2, 9,
927 -9, -1, -20, -2, 4, -4, 1, -5, 21, 5, -21, -1, 1, -22, -1, 2,
928 22, -2, 10, 1, -10, 23, 1, 4, -23, 1, 2, -1, -2, -4, -7, 1,
929 7, -24, -1, 24, -1, -1, 1, 3, -1, -25, 25, 4, -3, -4, 11, -11,
930 26, -26, 6, 1, 1, -6, -5, -3, 3, 5, -1, -27, 27, 1, 4, -4,
931 -1, -8, -1, 28, 2, 8, -12, -28, -2, -2, 2, 12, -1, 29, 1, -29,
932 30, -30, 5, -5, 1, -31, -1, 3, 31, -1, 1, 1, -3, -13, 1, -7,
933 -1, -32, 13, 7, 32, 33, -33, -1, -9, -34, 9, 34, -6, 5, 6, -5}
939 {1, 1, 0, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 0, 2, 2,
940 4, 1, 4, 1, 1, 1, 5, 5, 1, 1, 6, 6, 2, 2, 1, 1,
941 3, 3, 7, 7, 1, 1, 8, 8, 1, 1, 2, 2, 1, 9, 1, 9,
942 4, 4, 10, 1, 1, 10, 1, 1, 11, 11, 3, 3, 1, 2, 1, 2,
943 1, 1, 12, 12, 5, 5, 1, 1, 13, 1, 1, 13, 2, 2, 1, 1,
944 6, 6, 1, 1, 4, 14, 4, 14, 3, 1, 3, 1, 1, 1, 15, 7,
945 15, 2, 2, 7, 1, 1, 1, 8, 1, 8, 16, 16, 1, 1, 1, 1,
946 2, 1, 1, 2, 1, 1, 3, 5, 5, 3, 4, 1, 1, 4, 1, 1,
947 17, 17, 9, 1, 1, 9, 2, 2, 1, 1, 10, 10, 1, 6, 1, 1,
948 6, 18, 1, 1, 18, 1, 1, 1, 2, 2, 3, 1, 3, 1, 1, 1,
949 4, 1, 19, 1, 19, 7, 1, 1, 20, 1, 4, 20, 1, 7, 11, 2,
950 1, 11, 21, 2, 8, 5, 1, 8, 1, 5, 21, 1, 1, 1, 22, 1,
951 1, 22, 1, 1, 3, 3, 1, 23, 2, 12, 24, 1, 1, 2, 1, 1,
952 12, 23, 1, 1, 24, 1, 1, 1, 4, 1, 1, 1, 2, 1, 6, 6,
953 4, 2, 1, 1, 1, 1, 1, 1, 1, 14, 13, 3, 1, 25, 9, 25,
954 14, 1, 9, 3, 13, 1, 1, 1, 1, 1, 10, 1, 1, 2, 10, 2},
957 {-20, -1, 0, 2, -2, 1, -1, 3, -3, 1, -1, 4, -4, 0, 2, -2,
958 1, 5, -1, -5, 6, -6, 1, -1, 7, -7, 1, -1, 3, -3, 8, -8,
959 2, -2, 1, -1, 9, -9, 1, -1, 10, -10, 4, -4, 11, 1, -11, -1,
960 2, -2, 1, 12, -12, -1, 13, -13, 1, -1, 3, -3, 14, 5, -14, -5,
961 -15, 15, -1, 1, 2, -2, 16, -16, 1, 17, -17, -1, 6, -6, 18, -18,
962 2, -2, -19, 19, -3, 1, 3, -1, 4, 20, -4, 1, -21, 21, 1, 2,
963 -1, -7, 7, -2, 22, -22, 23, 2, -23, -2, 1, -1, -24, 24, -25, 25,
964 -8, -26, 26, 8, -27, 27, 5, 3, -3, -5, -4, 28, -28, 4, 29, -29,
965 1, -1, -2, -30, 30, 2, 9, -9, -31, 31, 2, -2, -32, 3, 32, -33,
966 -3, 1, 33, -34, -1, 34, -35, 35, -10, 10, -6, 36, 6, -36, 37, -37,
967 -5, 38, 1, -38, -1, 3, 39, -39, -1, 40, 5, 1, -40, -3, 2, -11,
968 -41, -2, 1, 11, -3, -4, 41, 3, 42, 4, -1, -43, -42, 43, 1, -44,
969 45, -1, 44, -45, -7, 7, -46, 1, -12, 2, 1, -47, 46, 12, 47, 48,
970 -2, -1, -48, 49, -1, -50, -49, 50, -6, -51, 51, 52, -13, 53, -4, 4,
971 6, 13, -53, -52, -54, 55, 54, -55, -56, -2, 2, -8, 56, 1, -3, -1,
972 2, 58, 3, 8, -2, 57, -58, -60, -59, -57, -3, 60, 59, -14, 3, 14}
978 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 5, 5, 1, 1, 6,
979 6, 2, 2, 7, 7, 8, 8, 1, 1, 3, 3, 9, 9, 10, 10, 1,
980 1, 2, 2, 4, 4, 11, 0, 11, 12, 12, 13, 13, 1, 1, 5, 5,
981 14, 14, 15, 16, 15, 16, 3, 3, 1, 6, 1, 6, 2, 2, 7, 7,
982 8, 8, 17, 17, 1, 1, 4, 4, 18, 18, 2, 2, 1, 19, 1, 20,
983 19, 20, 21, 21, 3, 3, 22, 22, 5, 5, 24, 1, 1, 23, 9, 23,
984 24, 9, 2, 2, 10, 1, 1, 10, 6, 6, 25, 4, 4, 25, 7, 7,
985 26, 8, 1, 8, 3, 1, 26, 3, 11, 11, 27, 27, 2, 28, 1, 2,
986 28, 1, 12, 12, 5, 5, 29, 13, 13, 29, 32, 1, 1, 33, 31, 30,
987 32, 4, 30, 33, 4, 31, 3, 14, 1, 1, 3, 34, 34, 2, 2, 14,
988 6, 6, 35, 36, 35, 36, 1, 15, 1, 16, 16, 15, 7, 9, 7, 9,
989 37, 8, 8, 37, 1, 1, 39, 2, 38, 39, 2, 40, 5, 38, 40, 5,
990 3, 3, 4, 4, 10, 10, 1, 1, 1, 1, 41, 2, 41, 2, 6, 6,
991 1, 1, 11, 42, 11, 43, 3, 42, 3, 17, 4, 43, 1, 17, 7, 1,
992 8, 44, 4, 7, 44, 5, 8, 2, 5, 1, 2, 48, 45, 1, 12, 45,
993 12, 48, 13, 13, 1, 9, 9, 46, 1, 46, 47, 47, 49, 18, 18, 49},
996 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 1, -1, 3, -3, 1,
997 -1, -2, 2, 1, -1, 1, -1, 4, -4, -2, 2, 1, -1, 1, -1, 5,
998 -5, -3, 3, 2, -2, 1, 0, -1, 1, -1, 1, -1, 6, -6, 2, -2,
999 1, -1, 1, 1, -1, -1, -3, 3, 7, 2, -7, -2, -4, 4, 2, -2,
1000 2, -2, 1, -1, 8, -8, 3, -3, 1, -1, -5, 5, 9, 1, -9, 1,
1001 -1, -1, 1, -1, -4, 4, 1, -1, 3, -3, 1, -10, 10, 1, 2, -1,
1002 -1, -2, 6, -6, 2, 11, -11, -2, 3, -3, 1, -4, 4, -1, 3, -3,
1003 1, 3, 12, -3, -5, -12, -1, 5, 2, -2, 1, -1, -7, 1, 13, 7,
1004 -1, -13, 2, -2, 4, -4, 1, 2, -2, -1, 1, 14, -14, 1, 1, 1,
1005 -1, -5, -1, -1, 5, -1, -6, 2, -15, 15, 6, 1, -1, -8, 8, -2,
1006 -4, 4, 1, 1, -1, -1, 16, 2, -16, -2, 2, -2, 4, 3, -4, -3,
1007 -1, -4, 4, 1, -17, 17, -1, -9, 1, 1, 9, 1, -5, -1, -1, 5,
1008 -7, 7, 6, -6, 3, -3, 18, -18, 19, -19, 1, -10, -1, 10, -5, 5,
1009 20, -20, -3, 1, 3, 1, 8, -1, -8, 2, 7, -1, -21, -2, 5, 21,
1010 5, -1, -7, -5, 1, -6, -5, -11, 6, 22, 11, 1, 1, -22, -3, -1,
1011 3, -1, 3, -3, -23, 4, -4, 1, 23, -1, 1, -1, 1, -2, 2, -1}
1017 {1, 1, 1, 1, 0, 2, 2, 1, 1, 3, 3, 0, 1, 1, 2, 2,
1018 4, 4, 1, 1, 5, 5, 1, 1, 2, 2, 3, 3, 6, 6, 1, 1,
1019 7, 7, 8, 1, 8, 2, 2, 1, 4, 4, 1, 3, 1, 3, 9, 9,
1020 2, 2, 1, 5, 1, 5, 10, 10, 1, 1, 11, 11, 3, 6, 3, 4,
1021 4, 6, 2, 2, 1, 12, 1, 12, 7, 13, 7, 13, 1, 1, 8, 8,
1022 2, 2, 14, 14, 16, 15, 16, 5, 5, 1, 3, 15, 1, 3, 4, 4,
1023 1, 1, 17, 17, 2, 2, 6, 6, 1, 18, 1, 18, 22, 21, 22, 21,
1024 25, 24, 25, 19, 9, 20, 9, 23, 19, 24, 20, 3, 23, 7, 3, 1,
1025 1, 7, 28, 26, 29, 5, 28, 26, 5, 8, 29, 4, 8, 27, 2, 2,
1026 4, 27, 1, 1, 10, 36, 10, 33, 33, 36, 30, 1, 32, 32, 1, 30,
1027 6, 31, 31, 35, 3, 6, 11, 11, 3, 2, 35, 2, 34, 1, 34, 1,
1028 37, 37, 12, 7, 12, 5, 41, 5, 4, 7, 1, 8, 13, 4, 1, 41,
1029 13, 38, 8, 38, 9, 1, 40, 40, 9, 1, 39, 2, 2, 49, 39, 42,
1030 3, 3, 14, 16, 49, 14, 16, 42, 43, 43, 6, 6, 15, 1, 1, 15,
1031 44, 44, 1, 1, 50, 48, 4, 5, 4, 7, 5, 2, 10, 10, 48, 7,
1032 50, 45, 2, 1, 45, 8, 8, 1, 46, 46, 3, 47, 47, 3, 1, 1},
1035 { 1, -1, 2, -2, 0, 1, -1, 3, -3, 1, -1, 0, 4, -4, 2, -2,
1036 1, -1, 5, -5, 1, -1, 6, -6, 3, -3, 2, -2, 1, -1, 7, -7,
1037 1, -1, 1, 8, -1, 4, -4, -8, 2, -2, 9, 3, -9, -3, 1, -1,
1038 5, -5, 10, 2, -10, -2, 1, -1, 11, -11, 1, -1, -4, 2, 4, 3,
1039 -3, -2, 6, -6, 12, 1, -12, -1, 2, 1, -2, -1, 13, -13, 2, -2,
1040 7, -7, 1, -1, 1, 1, -1, 3, -3, 14, 5, -1, -14, -5, 4, -4,
1041 15, -15, 1, -1, 8, -8, -3, 3, 16, 1, -16, -1, 1, 1, -1, -1,
1042 1, 1, -1, 1, 2, 1, -2, 1, -1, -1, -1, 6, -1, 3, -6, 17,
1043 -17, -3, 1, 1, 1, 4, -1, -1, -4, 3, -1, 5, -3, -1, -9, 9,
1044 -5, 1, 18, -18, 2, 1, -2, 1, -1, -1, 1, 19, -1, 1, -19, -1,
1045 4, 1, -1, 1, 7, -4, -2, 2, -7, 10, -1, -10, 1, 20, -1, -20,
1046 1, -1, 2, 4, -2, 5, 1, -5, 6, -4, 21, 4, 2, -6, -21, -1,
1047 -2, 1, -4, -1, -3, 22, -1, 1, 3, -22, -1, 11, -11, 1, 1, 1,
1048 8, -8, 2, 2, -1, -2, -2, -1, 1, -1, -5, 5, 2, 23, -23, -2,
1049 1, -1, 24, -24, -1, -1, 7, 6, -7, 5, -6, 12, -3, 3, 1, -5,
1050 1, 1, -12, 25, -1, -5, 5, -25, -1, 1, 9, 1, -1, -9, 26, -26}