InterFrameDecompressor.cpp

/***********************************************************************
InterFrameDecompressor - Class to decompress the difference between two
bathymetry or water level grids.
Copyright (c) 2023 Oliver Kreylos

This file is part of the Augmented Reality Sandbox (SARndbox).

The Augmented Reality Sandbox is free software; you can redistribute it
and/or modify it under the terms of the GNU General Public License as
published by the Free Software Foundation; either version 2 of the
License, or (at your option) any later version.

The Augmented Reality Sandbox is distributed in the hope that it will be
useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License along
with the Augmented Reality Sandbox; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
***********************************************************************/

#include "InterFrameDecompressor.h"

#include <stdexcept>

#include "HuffmanBuilder.h"

namespace {

/******************************************************
Huffman decoding tree for the inter-frame decompressor:
******************************************************/

static const HuffmanBuilder::Node interFrameDecompressorTree[]=
	{
	{~0U,1U,908U},{~0U,2U,3U},{257U,0U,0U},{~0U,4U,613U},{~0U,5U,448U},{~0U,6U,141U},{~0U,7U,8U},{516U,0U,0U},
	{~0U,9U,140U},{~0U,10U,119U},{~0U,11U,36U},{~0U,12U,35U},{~0U,13U,14U},{582U,0U,0U},{~0U,15U,30U},{~0U,16U,17U},
	{632U,0U,0U},{~0U,18U,29U},{~0U,19U,28U},{~0U,20U,21U},{861U,0U,0U},{~0U,22U,25U},{~0U,23U,24U},{44U,0U,0U},
	{411U,0U,0U},{~0U,26U,27U},{999U,0U,0U},{998U,0U,0U},{721U,0U,0U},{668U,0U,0U},{~0U,31U,34U},{~0U,32U,33U},
	{319U,0U,0U},{188U,0U,0U},{633U,0U,0U},{263U,0U,0U},{~0U,37U,56U},{~0U,38U,55U},{~0U,39U,50U},{~0U,40U,49U},
	{~0U,41U,46U},{~0U,42U,43U},{341U,0U,0U},{~0U,44U,45U},{864U,0U,0U},{113U,0U,0U},{~0U,47U,48U},{725U,0U,0U},
	{149U,0U,0U},{224U,0U,0U},{~0U,51U,54U},{~0U,52U,53U},{187U,0U,0U},{669U,0U,0U},{296U,0U,0U},{249U,0U,0U},
	{~0U,57U,58U},{268U,0U,0U},{~0U,59U,94U},{~0U,60U,87U},{~0U,61U,78U},{~0U,62U,69U},{~0U,63U,64U},{370U,0U,0U},
	{~0U,65U,68U},{~0U,66U,67U},{43U,0U,0U},{997U,0U,0U},{78U,0U,0U},{~0U,70U,71U},{865U,0U,0U},{~0U,72U,77U},
	{~0U,73U,76U},{~0U,74U,75U},{5U,0U,0U},{7U,0U,0U},{1001U,0U,0U},{77U,0U,0U},{~0U,79U,80U},{148U,0U,0U},
	{~0U,81U,82U},{112U,0U,0U},{~0U,83U,84U},{931U,0U,0U},{~0U,85U,86U},{39U,0U,0U},{1002U,0U,0U},{~0U,88U,93U},
	{~0U,89U,90U},{343U,0U,0U},{~0U,91U,92U},{369U,0U,0U},{866U,0U,0U},{670U,0U,0U},{~0U,95U,118U},{~0U,96U,115U},
	{~0U,97U,98U},{724U,0U,0U},{~0U,99U,102U},{~0U,100U,101U},{394U,0U,0U},{79U,0U,0U},{~0U,103U,104U},{930U,0U,0U},
	{~0U,105U,106U},{1000U,0U,0U},{~0U,107U,114U},{~0U,108U,111U},{~0U,109U,110U},{498U,0U,0U},{486U,0U,0U},{~0U,112U,113U},
	{494U,0U,0U},{497U,0U,0U},{447U,0U,0U},{~0U,116U,117U},{729U,0U,0U},{727U,0U,0U},{223U,0U,0U},{~0U,120U,139U},
	{~0U,121U,122U},{563U,0U,0U},{~0U,123U,124U},{583U,0U,0U},{~0U,125U,126U},{606U,0U,0U},{~0U,127U,138U},{~0U,128U,137U},
	{~0U,129U,130U},{342U,0U,0U},{~0U,131U,136U},{~0U,132U,133U},{932U,0U,0U},{~0U,134U,135U},{412U,0U,0U},{42U,0U,0U},
	{371U,0U,0U},{186U,0U,0U},{634U,0U,0U},{546U,0U,0U},{520U,0U,0U},{~0U,142U,305U},{~0U,143U,252U},{~0U,144U,145U},
	{531U,0U,0U},{~0U,146U,197U},{~0U,147U,172U},{~0U,148U,151U},{~0U,149U,150U},{278U,0U,0U},{242U,0U,0U},{~0U,152U,171U},
	{~0U,153U,170U},{~0U,154U,169U},{~0U,155U,156U},{730U,0U,0U},{~0U,157U,164U},{~0U,158U,163U},{~0U,159U,160U},{1004U,0U,0U},
	{~0U,161U,162U},{6U,0U,0U},{446U,0U,0U},{75U,0U,0U},{~0U,165U,166U},{74U,0U,0U},{~0U,167U,168U},{1003U,0U,0U},
	{414U,0U,0U},{671U,0U,0U},{297U,0U,0U},{607U,0U,0U},{~0U,173U,174U},{584U,0U,0U},{~0U,175U,182U},{~0U,176U,181U},
	{~0U,177U,180U},{~0U,178U,179U},{731U,0U,0U},{733U,0U,0U},{185U,0U,0U},{222U,0U,0U},{~0U,183U,196U},{~0U,184U,189U},
	{~0U,185U,186U},{726U,0U,0U},{~0U,187U,188U},{867U,0U,0U},{868U,0U,0U},{~0U,190U,191U},{728U,0U,0U},{~0U,192U,195U},
	{~0U,193U,194U},{935U,0U,0U},{933U,0U,0U},{109U,0U,0U},{635U,0U,0U},{~0U,198U,199U},{564U,0U,0U},{~0U,200U,219U},
	{~0U,201U,208U},{~0U,202U,207U},{~0U,203U,204U},{673U,0U,0U},{~0U,205U,206U},{344U,0U,0U},{732U,0U,0U},{298U,0U,0U},
	{~0U,209U,212U},{~0U,210U,211U},{320U,0U,0U},{672U,0U,0U},{~0U,213U,214U},{184U,0U,0U},{~0U,215U,218U},{~0U,216U,217U},
	{111U,0U,0U},{870U,0U,0U},{147U,0U,0U},{~0U,220U,251U},{~0U,221U,222U},{221U,0U,0U},{~0U,223U,240U},{~0U,224U,225U},
	{735U,0U,0U},{~0U,226U,235U},{~0U,227U,234U},{~0U,228U,229U},{1011U,0U,0U},{~0U,230U,231U},{4U,0U,0U},{~0U,232U,233U},
	{462U,0U,0U},{463U,0U,0U},{937U,0U,0U},{~0U,236U,237U},{938U,0U,0U},{~0U,238U,239U},{40U,0U,0U},{1006U,0U,0U},
	{~0U,241U,244U},{~0U,242U,243U},{110U,0U,0U},{871U,0U,0U},{~0U,245U,246U},{872U,0U,0U},{~0U,247U,248U},{934U,0U,0U},
	{~0U,249U,250U},{413U,0U,0U},{1005U,0U,0U},{608U,0U,0U},{~0U,253U,304U},{~0U,254U,255U},{547U,0U,0U},{~0U,256U,287U},
	{~0U,257U,286U},{~0U,258U,265U},{~0U,259U,264U},{~0U,260U,261U},{183U,0U,0U},{~0U,262U,263U},{734U,0U,0U},{345U,0U,0U},
	{636U,0U,0U},{~0U,266U,275U},{~0U,267U,274U},{~0U,268U,273U},{~0U,269U,270U},{873U,0U,0U},{~0U,271U,272U},{73U,0U,0U},
	{76U,0U,0U},{146U,0U,0U},{674U,0U,0U},{~0U,276U,285U},{~0U,277U,284U},{~0U,278U,283U},{~0U,279U,280U},{396U,0U,0U},
	{~0U,281U,282U},{420U,0U,0U},{38U,0U,0U},{869U,0U,0U},{736U,0U,0U},{321U,0U,0U},{585U,0U,0U},{~0U,288U,293U},
	{~0U,289U,290U},{279U,0U,0U},{~0U,291U,292U},{637U,0U,0U},{299U,0U,0U},{~0U,294U,303U},{~0U,295U,296U},{220U,0U,0U},
	{~0U,297U,302U},{~0U,298U,301U},{~0U,299U,300U},{372U,0U,0U},{876U,0U,0U},{145U,0U,0U},{675U,0U,0U},{241U,0U,0U},
	{532U,0U,0U},{~0U,306U,447U},{~0U,307U,400U},{~0U,308U,333U},{~0U,309U,310U},{565U,0U,0U},{~0U,311U,332U},{~0U,312U,331U},
	{~0U,313U,326U},{~0U,314U,315U},{182U,0U,0U},{~0U,316U,317U},{737U,0U,0U},{~0U,318U,319U},{874U,0U,0U},{~0U,320U,323U},
	{~0U,321U,322U},{1009U,0U,0U},{1008U,0U,0U},{~0U,324U,325U},{1007U,0U,0U},{41U,0U,0U},{~0U,327U,330U},{~0U,328U,329U},
	{346U,0U,0U},{739U,0U,0U},{676U,0U,0U},{609U,0U,0U},{269U,0U,0U},{~0U,334U,359U},{~0U,335U,358U},{~0U,336U,351U},
	{~0U,337U,350U},{~0U,338U,349U},{~0U,339U,342U},{~0U,340U,341U},{108U,0U,0U},{875U,0U,0U},{~0U,343U,348U},{~0U,344U,347U},
	{~0U,345U,346U},{37U,0U,0U},{415U,0U,0U},{940U,0U,0U},{878U,0U,0U},{181U,0U,0U},{219U,0U,0U},{~0U,352U,357U},
	{~0U,353U,356U},{~0U,354U,355U},{738U,0U,0U},{144U,0U,0U},{677U,0U,0U},{638U,0U,0U},{586U,0U,0U},{~0U,360U,373U},
	{~0U,361U,362U},{610U,0U,0U},{~0U,363U,364U},{300U,0U,0U},{~0U,365U,366U},{179U,0U,0U},{~0U,367U,368U},{741U,0U,0U},
	{~0U,369U,372U},{~0U,370U,371U},{395U,0U,0U},{936U,0U,0U},{373U,0U,0U},{~0U,374U,399U},{~0U,375U,398U},{~0U,376U,377U},
	{322U,0U,0U},{~0U,378U,397U},{~0U,379U,396U},{~0U,380U,395U},{~0U,381U,390U},{~0U,382U,389U},{~0U,383U,386U},{~0U,384U,385U},
	{496U,0U,0U},{500U,0U,0U},{~0U,387U,388U},{491U,0U,0U},{495U,0U,0U},{3U,0U,0U},{~0U,391U,392U},{448U,0U,0U},
	{~0U,393U,394U},{466U,0U,0U},{465U,0U,0U},{939U,0U,0U},{877U,0U,0U},{740U,0U,0U},{218U,0U,0U},{280U,0U,0U},
	{~0U,401U,402U},{548U,0U,0U},{~0U,403U,404U},{566U,0U,0U},{~0U,405U,446U},{~0U,406U,417U},{~0U,407U,416U},{~0U,408U,415U},
	{~0U,409U,414U},{~0U,410U,411U},{374U,0U,0U},{~0U,412U,413U},{72U,0U,0U},{69U,0U,0U},{744U,0U,0U},{180U,0U,0U},
	{639U,0U,0U},{~0U,418U,427U},{~0U,419U,420U},{678U,0U,0U},{~0U,421U,422U},{746U,0U,0U},{~0U,423U,424U},{106U,0U,0U},
	{~0U,425U,426U},{941U,0U,0U},{71U,0U,0U},{~0U,428U,431U},{~0U,429U,430U},{143U,0U,0U},{347U,0U,0U},{~0U,432U,439U},
	{~0U,433U,434U},{107U,0U,0U},{~0U,435U,436U},{942U,0U,0U},{~0U,437U,438U},{421U,0U,0U},{1012U,0U,0U},{~0U,440U,445U},
	{~0U,441U,444U},{~0U,442U,443U},{419U,0U,0U},{416U,0U,0U},{70U,0U,0U},{879U,0U,0U},{587U,0U,0U},{521U,0U,0U},
	{~0U,449U,450U},{258U,0U,0U},{~0U,451U,564U},{~0U,452U,455U},{~0U,453U,454U},{253U,0U,0U},{533U,0U,0U},{~0U,456U,515U},
	{~0U,457U,514U},{~0U,458U,489U},{~0U,459U,468U},{~0U,460U,467U},{~0U,461U,462U},{301U,0U,0U},{~0U,463U,466U},{~0U,464U,465U},
	{742U,0U,0U},{743U,0U,0U},{178U,0U,0U},{240U,0U,0U},{~0U,469U,488U},{~0U,470U,471U},{217U,0U,0U},{~0U,472U,487U},
	{~0U,473U,486U},{~0U,474U,479U},{~0U,475U,476U},{946U,0U,0U},{~0U,477U,478U},{1013U,0U,0U},{418U,0U,0U},{~0U,480U,485U},
	{~0U,481U,484U},{~0U,482U,483U},{1U,0U,0U},{2U,0U,0U},{36U,0U,0U},{68U,0U,0U},{142U,0U,0U},{679U,0U,0U},
	{611U,0U,0U},{~0U,490U,513U},{~0U,491U,500U},{~0U,492U,499U},{~0U,493U,498U},{~0U,494U,495U},{745U,0U,0U},{~0U,496U,497U},
	{105U,0U,0U},{880U,0U,0U},{680U,0U,0U},{216U,0U,0U},{~0U,501U,502U},{640U,0U,0U},{~0U,503U,504U},{323U,0U,0U},
	{~0U,505U,512U},{~0U,506U,511U},{~0U,507U,510U},{~0U,508U,509U},{417U,0U,0U},{1010U,0U,0U},{945U,0U,0U},{375U,0U,0U},
	{348U,0U,0U},{248U,0U,0U},{549U,0U,0U},{~0U,516U,555U},{~0U,517U,518U},{567U,0U,0U},{~0U,519U,520U},{588U,0U,0U},
	{~0U,521U,522U},{612U,0U,0U},{~0U,523U,532U},{~0U,524U,525U},{177U,0U,0U},{~0U,526U,527U},{141U,0U,0U},{~0U,528U,531U},
	{~0U,529U,530U},{943U,0U,0U},{397U,0U,0U},{102U,0U,0U},{~0U,533U,538U},{~0U,534U,535U},{747U,0U,0U},{~0U,536U,537U},
	{881U,0U,0U},{103U,0U,0U},{~0U,539U,540U},{749U,0U,0U},{~0U,541U,552U},{~0U,542U,551U},{~0U,543U,544U},{34U,0U,0U},
	{~0U,545U,550U},{~0U,546U,547U},{464U,0U,0U},{~0U,548U,549U},{488U,0U,0U},{503U,0U,0U},{449U,0U,0U},{944U,0U,0U},
	{~0U,553U,554U},{948U,0U,0U},{949U,0U,0U},{~0U,556U,557U},{264U,0U,0U},{~0U,558U,563U},{~0U,559U,560U},{281U,0U,0U},
	{~0U,561U,562U},{641U,0U,0U},{215U,0U,0U},{270U,0U,0U},{~0U,565U,612U},{~0U,566U,567U},{534U,0U,0U},{~0U,568U,569U},
	{261U,0U,0U},{~0U,570U,571U},{1025U,0U,0U},{~0U,572U,597U},{~0U,573U,594U},{~0U,574U,579U},{~0U,575U,576U},{324U,0U,0U},
	{~0U,577U,578U},{748U,0U,0U},{140U,0U,0U},{~0U,580U,581U},{681U,0U,0U},{~0U,582U,593U},{~0U,583U,588U},{~0U,584U,587U},
	{~0U,585U,586U},{32U,0U,0U},{1015U,0U,0U},{950U,0U,0U},{~0U,589U,590U},{398U,0U,0U},{~0U,591U,592U},{1017U,0U,0U},
	{33U,0U,0U},{349U,0U,0U},{~0U,595U,596U},{302U,0U,0U},{214U,0U,0U},{~0U,598U,611U},{~0U,599U,610U},{~0U,600U,603U},
	{~0U,601U,602U},{752U,0U,0U},{754U,0U,0U},{~0U,604U,609U},{~0U,605U,606U},{882U,0U,0U},{~0U,607U,608U},{66U,0U,0U},
	{947U,0U,0U},{139U,0U,0U},{642U,0U,0U},{613U,0U,0U},{522U,0U,0U},{~0U,614U,615U},{514U,0U,0U},{~0U,616U,617U},
	{515U,0U,0U},{~0U,618U,807U},{~0U,619U,708U},{~0U,620U,659U},{~0U,621U,658U},{~0U,622U,623U},{568U,0U,0U},{~0U,624U,625U},
	{589U,0U,0U},{~0U,626U,651U},{~0U,627U,634U},{~0U,628U,633U},{~0U,629U,630U},{751U,0U,0U},{~0U,631U,632U},{104U,0U,0U},
	{884U,0U,0U},{176U,0U,0U},{~0U,635U,636U},{682U,0U,0U},{~0U,637U,638U},{750U,0U,0U},{~0U,639U,650U},{~0U,640U,641U},
	{67U,0U,0U},{~0U,642U,643U},{424U,0U,0U},{~0U,644U,645U},{0U,0U,0U},{~0U,646U,647U},{467U,0U,0U},{~0U,648U,649U},
	{499U,0U,0U},{501U,0U,0U},{886U,0U,0U},{~0U,652U,653U},{213U,0U,0U},{~0U,654U,657U},{~0U,655U,656U},{138U,0U,0U},
	{350U,0U,0U},{683U,0U,0U},{550U,0U,0U},{~0U,660U,693U},{~0U,661U,692U},{~0U,662U,665U},{~0U,663U,664U},{282U,0U,0U},
	{239U,0U,0U},{~0U,666U,689U},{~0U,667U,668U},{643U,0U,0U},{~0U,669U,680U},{~0U,670U,679U},{~0U,671U,672U},{883U,0U,0U},
	{~0U,673U,676U},{~0U,674U,675U},{1014U,0U,0U},{1016U,0U,0U},{~0U,677U,678U},{422U,0U,0U},{29U,0U,0U},{756U,0U,0U},
	{~0U,681U,684U},{~0U,682U,683U},{885U,0U,0U},{376U,0U,0U},{~0U,685U,688U},{~0U,686U,687U},{63U,0U,0U},{400U,0U,0U},
	{101U,0U,0U},{~0U,690U,691U},{303U,0U,0U},{212U,0U,0U},{251U,0U,0U},{~0U,694U,707U},{~0U,695U,706U},{~0U,696U,697U},
	{614U,0U,0U},{~0U,698U,701U},{~0U,699U,700U},{175U,0U,0U},{325U,0U,0U},{~0U,702U,703U},{684U,0U,0U},{~0U,704U,705U},
	{137U,0U,0U},{758U,0U,0U},{590U,0U,0U},{569U,0U,0U},{~0U,709U,710U},{535U,0U,0U},{~0U,711U,712U},{551U,0U,0U},
	{~0U,713U,770U},{~0U,714U,757U},{~0U,715U,736U},{~0U,716U,735U},{~0U,717U,726U},{~0U,718U,725U},{~0U,719U,720U},{377U,0U,0U},
	{~0U,721U,724U},{~0U,722U,723U},{1019U,0U,0U},{1020U,0U,0U},{399U,0U,0U},{761U,0U,0U},{~0U,727U,734U},{~0U,728U,729U},
	{887U,0U,0U},{~0U,730U,731U},{65U,0U,0U},{~0U,732U,733U},{35U,0U,0U},{28U,0U,0U},{753U,0U,0U},{211U,0U,0U},
	{~0U,737U,742U},{~0U,738U,741U},{~0U,739U,740U},{757U,0U,0U},{760U,0U,0U},{174U,0U,0U},{~0U,743U,754U},{~0U,744U,753U},
	{~0U,745U,750U},{~0U,746U,749U},{~0U,747U,748U},{425U,0U,0U},{1018U,0U,0U},{951U,0U,0U},{~0U,751U,752U},{62U,0U,0U},
	{955U,0U,0U},{755U,0U,0U},{~0U,755U,756U},{767U,0U,0U},{766U,0U,0U},{~0U,758U,769U},{~0U,759U,760U},{644U,0U,0U},
	{~0U,761U,766U},{~0U,762U,763U},{765U,0U,0U},{~0U,764U,765U},{100U,0U,0U},{378U,0U,0U},{~0U,767U,768U},{763U,0U,0U},
	{136U,0U,0U},{615U,0U,0U},{~0U,771U,780U},{~0U,772U,773U},{283U,0U,0U},{~0U,774U,779U},{~0U,775U,776U},{326U,0U,0U},
	{~0U,777U,778U},{759U,0U,0U},{351U,0U,0U},{210U,0U,0U},{~0U,781U,794U},{~0U,782U,793U},{~0U,783U,792U},{~0U,784U,785U},
	{762U,0U,0U},{~0U,786U,791U},{~0U,787U,788U},{64U,0U,0U},{~0U,789U,790U},{30U,0U,0U},{423U,0U,0U},{888U,0U,0U},
	{685U,0U,0U},{304U,0U,0U},{~0U,795U,806U},{~0U,796U,797U},{686U,0U,0U},{~0U,798U,805U},{~0U,799U,800U},{890U,0U,0U},
	{~0U,801U,804U},{~0U,802U,803U},{31U,0U,0U},{1022U,0U,0U},{401U,0U,0U},{135U,0U,0U},{209U,0U,0U},{~0U,808U,809U},
	{523U,0U,0U},{~0U,810U,907U},{~0U,811U,824U},{~0U,812U,823U},{~0U,813U,822U},{~0U,814U,815U},{238U,0U,0U},{~0U,816U,821U},
	{~0U,817U,818U},{173U,0U,0U},{~0U,819U,820U},{773U,0U,0U},{134U,0U,0U},{645U,0U,0U},{591U,0U,0U},{570U,0U,0U},
	{~0U,825U,848U},{~0U,826U,847U},{~0U,827U,846U},{~0U,828U,841U},{~0U,829U,832U},{~0U,830U,831U},{764U,0U,0U},{770U,0U,0U},
	{~0U,833U,840U},{~0U,834U,835U},{99U,0U,0U},{~0U,836U,837U},{953U,0U,0U},{~0U,838U,839U},{1021U,0U,0U},{426U,0U,0U},
	{352U,0U,0U},{~0U,842U,843U},{687U,0U,0U},{~0U,844U,845U},{768U,0U,0U},{774U,0U,0U},{616U,0U,0U},{271U,0U,0U},
	{~0U,849U,868U},{~0U,850U,853U},{~0U,851U,852U},{305U,0U,0U},{646U,0U,0U},{~0U,854U,861U},{~0U,855U,860U},{~0U,856U,859U},
	{~0U,857U,858U},{889U,0U,0U},{98U,0U,0U},{778U,0U,0U},{327U,0U,0U},{~0U,862U,865U},{~0U,863U,864U},{776U,0U,0U},
	{775U,0U,0U},{~0U,866U,867U},{771U,0U,0U},{782U,0U,0U},{~0U,869U,880U},{~0U,870U,879U},{~0U,871U,878U},{~0U,872U,877U},
	{~0U,873U,876U},{~0U,874U,875U},{952U,0U,0U},{954U,0U,0U},{97U,0U,0U},{777U,0U,0U},{172U,0U,0U},{208U,0U,0U},
	{~0U,881U,902U},{~0U,882U,883U},{171U,0U,0U},{~0U,884U,901U},{~0U,885U,896U},{~0U,886U,895U},{~0U,887U,894U},{~0U,888U,889U},
	{450U,0U,0U},{~0U,890U,893U},{~0U,891U,892U},{502U,0U,0U},{506U,0U,0U},{469U,0U,0U},{1023U,0U,0U},{61U,0U,0U},
	{~0U,897U,898U},{956U,0U,0U},{~0U,899U,900U},{27U,0U,0U},{26U,0U,0U},{769U,0U,0U},{~0U,903U,906U},{~0U,904U,905U},
	{789U,0U,0U},{353U,0U,0U},{688U,0U,0U},{260U,0U,0U},{~0U,909U,910U},{255U,0U,0U},{~0U,911U,1606U},{~0U,912U,1251U},
	{~0U,913U,1002U},{~0U,914U,915U},{517U,0U,0U},{~0U,916U,959U},{~0U,917U,918U},{536U,0U,0U},{~0U,919U,920U},{552U,0U,0U},
	{~0U,921U,940U},{~0U,922U,923U},{592U,0U,0U},{~0U,924U,925U},{284U,0U,0U},{~0U,926U,935U},{~0U,927U,932U},{~0U,928U,929U},
	{784U,0U,0U},{~0U,930U,931U},{896U,0U,0U},{893U,0U,0U},{~0U,933U,934U},{354U,0U,0U},{781U,0U,0U},{~0U,936U,939U},
	{~0U,937U,938U},{772U,0U,0U},{787U,0U,0U},{689U,0U,0U},{~0U,941U,958U},{~0U,942U,957U},{~0U,943U,956U},{~0U,944U,953U},
	{~0U,945U,952U},{~0U,946U,947U},{892U,0U,0U},{~0U,948U,949U},{957U,0U,0U},{~0U,950U,951U},{1024U,0U,0U},{427U,0U,0U},
	{133U,0U,0U},{~0U,954U,955U},{132U,0U,0U},{783U,0U,0U},{647U,0U,0U},{617U,0U,0U},{247U,0U,0U},{~0U,960U,1001U},
	{~0U,961U,1000U},{~0U,962U,963U},{571U,0U,0U},{~0U,964U,973U},{~0U,965U,966U},{237U,0U,0U},{~0U,967U,968U},{207U,0U,0U},
	{~0U,969U,972U},{~0U,970U,971U},{779U,0U,0U},{790U,0U,0U},{170U,0U,0U},{~0U,974U,993U},{~0U,975U,986U},{~0U,976U,983U},
	{~0U,977U,982U},{~0U,978U,979U},{900U,0U,0U},{~0U,980U,981U},{959U,0U,0U},{60U,0U,0U},{780U,0U,0U},{~0U,984U,985U},
	{788U,0U,0U},{786U,0U,0U},{~0U,987U,992U},{~0U,988U,989U},{131U,0U,0U},{~0U,990U,991U},{96U,0U,0U},{895U,0U,0U},
	{328U,0U,0U},{~0U,994U,995U},{306U,0U,0U},{~0U,996U,999U},{~0U,997U,998U},{791U,0U,0U},{793U,0U,0U},{690U,0U,0U},
	{553U,0U,0U},{537U,0U,0U},{~0U,1003U,1142U},{~0U,1004U,1005U},{524U,0U,0U},{~0U,1006U,1077U},{~0U,1007U,1042U},{~0U,1008U,1009U},
	{265U,0U,0U},{~0U,1010U,1041U},{~0U,1011U,1034U},{~0U,1012U,1013U},{648U,0U,0U},{~0U,1014U,1029U},{~0U,1015U,1026U},{~0U,1016U,1017U},
	{891U,0U,0U},{~0U,1018U,1019U},{958U,0U,0U},{~0U,1020U,1025U},{~0U,1021U,1022U},{451U,0U,0U},{~0U,1023U,1024U},{474U,0U,0U},
	{472U,0U,0U},{430U,0U,0U},{~0U,1027U,1028U},{899U,0U,0U},{898U,0U,0U},{~0U,1030U,1031U},{785U,0U,0U},{~0U,1032U,1033U},
	{380U,0U,0U},{894U,0U,0U},{~0U,1035U,1036U},{307U,0U,0U},{~0U,1037U,1040U},{~0U,1038U,1039U},{794U,0U,0U},{797U,0U,0U},
	{169U,0U,0U},{593U,0U,0U},{~0U,1043U,1076U},{~0U,1044U,1047U},{~0U,1045U,1046U},{618U,0U,0U},{285U,0U,0U},{~0U,1048U,1051U},
	{~0U,1049U,1050U},{206U,0U,0U},{513U,0U,0U},{~0U,1052U,1065U},{~0U,1053U,1058U},{~0U,1054U,1057U},{~0U,1055U,1056U},{901U,0U,0U},
	{94U,0U,0U},{795U,0U,0U},{~0U,1059U,1064U},{~0U,1060U,1063U},{~0U,1061U,1062U},{965U,0U,0U},{59U,0U,0U},{381U,0U,0U},
	{792U,0U,0U},{~0U,1066U,1067U},{691U,0U,0U},{~0U,1068U,1069U},{355U,0U,0U},{~0U,1070U,1071U},{897U,0U,0U},{~0U,1072U,1075U},
	{~0U,1073U,1074U},{431U,0U,0U},{429U,0U,0U},{57U,0U,0U},{572U,0U,0U},{~0U,1078U,1141U},{~0U,1079U,1108U},{~0U,1080U,1107U},
	{~0U,1081U,1082U},{236U,0U,0U},{~0U,1083U,1096U},{~0U,1084U,1087U},{~0U,1085U,1086U},{804U,0U,0U},{800U,0U,0U},{~0U,1088U,1095U},
	{~0U,1089U,1094U},{~0U,1090U,1093U},{~0U,1091U,1092U},{432U,0U,0U},{435U,0U,0U},{960U,0U,0U},{379U,0U,0U},{799U,0U,0U},
	{~0U,1097U,1098U},{329U,0U,0U},{~0U,1099U,1106U},{~0U,1100U,1105U},{~0U,1101U,1102U},{966U,0U,0U},{~0U,1103U,1104U},{25U,0U,0U},
	{21U,0U,0U},{903U,0U,0U},{796U,0U,0U},{272U,0U,0U},{~0U,1109U,1140U},{~0U,1110U,1121U},{~0U,1111U,1120U},{~0U,1112U,1119U},
	{~0U,1113U,1114U},{815U,0U,0U},{~0U,1115U,1116U},{95U,0U,0U},{~0U,1117U,1118U},{402U,0U,0U},{56U,0U,0U},{693U,0U,0U},
	{649U,0U,0U},{~0U,1122U,1127U},{~0U,1123U,1126U},{~0U,1124U,1125U},{130U,0U,0U},{798U,0U,0U},{692U,0U,0U},{~0U,1128U,1131U},
	{~0U,1129U,1130U},{802U,0U,0U},{357U,0U,0U},{~0U,1132U,1139U},{~0U,1133U,1136U},{~0U,1134U,1135U},{975U,0U,0U},{58U,0U,0U},
	{~0U,1137U,1138U},{961U,0U,0U},{963U,0U,0U},{803U,0U,0U},{594U,0U,0U},{554U,0U,0U},{~0U,1143U,1250U},{~0U,1144U,1249U},
	{~0U,1145U,1180U},{~0U,1146U,1179U},{~0U,1147U,1156U},{~0U,1148U,1149U},{619U,0U,0U},{~0U,1150U,1155U},{~0U,1151U,1152U},{168U,0U,0U},
	{~0U,1153U,1154U},{801U,0U,0U},{808U,0U,0U},{205U,0U,0U},{~0U,1157U,1176U},{~0U,1158U,1165U},{~0U,1159U,1162U},{~0U,1160U,1161U},
	{810U,0U,0U},{812U,0U,0U},{~0U,1163U,1164U},{356U,0U,0U},{813U,0U,0U},{~0U,1166U,1169U},{~0U,1167U,1168U},{809U,0U,0U},
	{811U,0U,0U},{~0U,1170U,1175U},{~0U,1171U,1172U},{93U,0U,0U},{~0U,1173U,1174U},{974U,0U,0U},{972U,0U,0U},{817U,0U,0U},
	{~0U,1177U,1178U},{308U,0U,0U},{204U,0U,0U},{573U,0U,0U},{~0U,1181U,1214U},{~0U,1182U,1197U},{~0U,1183U,1184U},{286U,0U,0U},
	{~0U,1185U,1196U},{~0U,1186U,1189U},{~0U,1187U,1188U},{806U,0U,0U},{129U,0U,0U},{~0U,1190U,1191U},{805U,0U,0U},{~0U,1192U,1195U},
	{~0U,1193U,1194U},{964U,0U,0U},{970U,0U,0U},{902U,0U,0U},{650U,0U,0U},{~0U,1198U,1213U},{~0U,1199U,1200U},{651U,0U,0U},
	{~0U,1201U,1204U},{~0U,1202U,1203U},{816U,0U,0U},{807U,0U,0U},{~0U,1205U,1212U},{~0U,1206U,1211U},{~0U,1207U,1210U},{~0U,1208U,1209U},
	{22U,0U,0U},{428U,0U,0U},{967U,0U,0U},{92U,0U,0U},{814U,0U,0U},{620U,0U,0U},{~0U,1215U,1216U},{595U,0U,0U},
	{~0U,1217U,1224U},{~0U,1218U,1221U},{~0U,1219U,1220U},{694U,0U,0U},{330U,0U,0U},{~0U,1222U,1223U},{167U,0U,0U},{166U,0U,0U},
	{~0U,1225U,1248U},{~0U,1226U,1227U},{695U,0U,0U},{~0U,1228U,1241U},{~0U,1229U,1240U},{~0U,1230U,1231U},{962U,0U,0U},{~0U,1232U,1233U},
	{24U,0U,0U},{~0U,1234U,1237U},{~0U,1235U,1236U},{479U,0U,0U},{470U,0U,0U},{~0U,1238U,1239U},{468U,0U,0U},{476U,0U,0U},
	{905U,0U,0U},{~0U,1242U,1247U},{~0U,1243U,1246U},{~0U,1244U,1245U},{20U,0U,0U},{434U,0U,0U},{976U,0U,0U},{91U,0U,0U},
	{203U,0U,0U},{538U,0U,0U},{525U,0U,0U},{~0U,1252U,1469U},{~0U,1253U,1394U},{~0U,1254U,1329U},{~0U,1255U,1306U},{~0U,1256U,1257U},
	{555U,0U,0U},{~0U,1258U,1301U},{~0U,1259U,1264U},{~0U,1260U,1261U},{235U,0U,0U},{~0U,1262U,1263U},{202U,0U,0U},{652U,0U,0U},
	{~0U,1265U,1276U},{~0U,1266U,1275U},{~0U,1267U,1274U},{~0U,1268U,1273U},{~0U,1269U,1270U},{906U,0U,0U},{~0U,1271U,1272U},{969U,0U,0U},
	{968U,0U,0U},{358U,0U,0U},{165U,0U,0U},{309U,0U,0U},{~0U,1277U,1278U},{201U,0U,0U},{~0U,1279U,1298U},{~0U,1280U,1283U},
	{~0U,1281U,1282U},{382U,0U,0U},{904U,0U,0U},{~0U,1284U,1287U},{~0U,1285U,1286U},{973U,0U,0U},{404U,0U,0U},{~0U,1288U,1297U},
	{~0U,1289U,1290U},{433U,0U,0U},{~0U,1291U,1296U},{~0U,1292U,1295U},{~0U,1293U,1294U},{504U,0U,0U},{511U,0U,0U},{477U,0U,0U},
	{454U,0U,0U},{971U,0U,0U},{~0U,1299U,1300U},{818U,0U,0U},{128U,0U,0U},{~0U,1302U,1305U},{~0U,1303U,1304U},{287U,0U,0U},
	{621U,0U,0U},{596U,0U,0U},{~0U,1307U,1328U},{~0U,1308U,1309U},{574U,0U,0U},{~0U,1310U,1327U},{~0U,1311U,1316U},{~0U,1312U,1313U},
	{310U,0U,0U},{~0U,1314U,1315U},{696U,0U,0U},{331U,0U,0U},{~0U,1317U,1318U},{653U,0U,0U},{~0U,1319U,1320U},{698U,0U,0U},
	{~0U,1321U,1326U},{~0U,1322U,1323U},{383U,0U,0U},{~0U,1324U,1325U},{977U,0U,0U},{54U,0U,0U},{823U,0U,0U},{246U,0U,0U},
	{252U,0U,0U},{~0U,1330U,1331U},{539U,0U,0U},{~0U,1332U,1393U},{~0U,1333U,1376U},{~0U,1334U,1349U},{~0U,1335U,1348U},{~0U,1336U,1347U},
	{~0U,1337U,1338U},{697U,0U,0U},{~0U,1339U,1340U},{359U,0U,0U},{~0U,1341U,1344U},{~0U,1342U,1343U},{985U,0U,0U},{403U,0U,0U},
	{~0U,1345U,1346U},{983U,0U,0U},{55U,0U,0U},{200U,0U,0U},{622U,0U,0U},{~0U,1350U,1351U},{234U,0U,0U},{~0U,1352U,1353U},
	{654U,0U,0U},{~0U,1354U,1361U},{~0U,1355U,1358U},{~0U,1356U,1357U},{89U,0U,0U},{907U,0U,0U},{~0U,1359U,1360U},{90U,0U,0U},
	{908U,0U,0U},{~0U,1362U,1363U},{819U,0U,0U},{~0U,1364U,1375U},{~0U,1365U,1368U},{~0U,1366U,1367U},{23U,0U,0U},{19U,0U,0U},
	{~0U,1369U,1374U},{~0U,1370U,1373U},{~0U,1371U,1372U},{471U,0U,0U},{480U,0U,0U},{453U,0U,0U},{437U,0U,0U},{88U,0U,0U},
	{~0U,1377U,1378U},{273U,0U,0U},{~0U,1379U,1390U},{~0U,1380U,1387U},{~0U,1381U,1382U},{164U,0U,0U},{~0U,1383U,1384U},{127U,0U,0U},
	{~0U,1385U,1386U},{909U,0U,0U},{384U,0U,0U},{~0U,1388U,1389U},{163U,0U,0U},{699U,0U,0U},{~0U,1391U,1392U},{655U,0U,0U},
	{311U,0U,0U},{556U,0U,0U},{~0U,1395U,1396U},{526U,0U,0U},{~0U,1397U,1468U},{~0U,1398U,1425U},{~0U,1399U,1400U},{575U,0U,0U},
	{~0U,1401U,1402U},{597U,0U,0U},{~0U,1403U,1424U},{~0U,1404U,1423U},{~0U,1405U,1420U},{~0U,1406U,1407U},{827U,0U,0U},{~0U,1408U,1411U},
	{~0U,1409U,1410U},{982U,0U,0U},{978U,0U,0U},{~0U,1412U,1419U},{~0U,1413U,1418U},{~0U,1414U,1415U},{452U,0U,0U},{~0U,1416U,1417U},
	{478U,0U,0U},{473U,0U,0U},{436U,0U,0U},{984U,0U,0U},{~0U,1421U,1422U},{825U,0U,0U},{829U,0U,0U},{199U,0U,0U},
	{288U,0U,0U},{~0U,1426U,1467U},{~0U,1427U,1456U},{~0U,1428U,1435U},{~0U,1429U,1430U},{198U,0U,0U},{~0U,1431U,1434U},{~0U,1432U,1433U},
	{821U,0U,0U},{822U,0U,0U},{332U,0U,0U},{~0U,1436U,1449U},{~0U,1437U,1440U},{~0U,1438U,1439U},{828U,0U,0U},{824U,0U,0U},
	{~0U,1441U,1442U},{830U,0U,0U},{~0U,1443U,1448U},{~0U,1444U,1445U},{979U,0U,0U},{~0U,1446U,1447U},{438U,0U,0U},{17U,0U,0U},
	{385U,0U,0U},{~0U,1450U,1453U},{~0U,1451U,1452U},{826U,0U,0U},{126U,0U,0U},{~0U,1454U,1455U},{820U,0U,0U},{834U,0U,0U},
	{~0U,1457U,1458U},{623U,0U,0U},{~0U,1459U,1460U},{312U,0U,0U},{~0U,1461U,1466U},{~0U,1462U,1463U},{831U,0U,0U},{~0U,1464U,1465U},
	{87U,0U,0U},{911U,0U,0U},{700U,0U,0U},{266U,0U,0U},{540U,0U,0U},{~0U,1470U,1471U},{518U,0U,0U},{~0U,1472U,1557U},
	{~0U,1473U,1538U},{~0U,1474U,1475U},{262U,0U,0U},{~0U,1476U,1509U},{~0U,1477U,1492U},{~0U,1478U,1491U},{~0U,1479U,1490U},{~0U,1480U,1487U},
	{~0U,1481U,1482U},{360U,0U,0U},{~0U,1483U,1484U},{913U,0U,0U},{~0U,1485U,1486U},{53U,0U,0U},{981U,0U,0U},{~0U,1488U,1489U},
	{832U,0U,0U},{838U,0U,0U},{197U,0U,0U},{233U,0U,0U},{~0U,1493U,1508U},{~0U,1494U,1503U},{~0U,1495U,1502U},{~0U,1496U,1501U},
	{~0U,1497U,1498U},{915U,0U,0U},{~0U,1499U,1500U},{987U,0U,0U},{980U,0U,0U},{124U,0U,0U},{703U,0U,0U},{~0U,1504U,1505U},
	{701U,0U,0U},{~0U,1506U,1507U},{833U,0U,0U},{836U,0U,0U},{289U,0U,0U},{~0U,1510U,1537U},{~0U,1511U,1532U},{~0U,1512U,1515U},
	{~0U,1513U,1514U},{162U,0U,0U},{160U,0U,0U},{~0U,1516U,1531U},{~0U,1517U,1518U},{841U,0U,0U},{~0U,1519U,1530U},{~0U,1520U,1521U},
	{52U,0U,0U},{~0U,1522U,1523U},{18U,0U,0U},{~0U,1524U,1529U},{~0U,1525U,1526U},{482U,0U,0U},{~0U,1527U,1528U},{510U,0U,0U},
	{505U,0U,0U},{455U,0U,0U},{910U,0U,0U},{333U,0U,0U},{~0U,1533U,1534U},{196U,0U,0U},{~0U,1535U,1536U},{334U,0U,0U},
	{161U,0U,0U},{598U,0U,0U},{~0U,1539U,1540U},{557U,0U,0U},{~0U,1541U,1542U},{576U,0U,0U},{~0U,1543U,1548U},{~0U,1544U,1547U},
	{~0U,1545U,1546U},{656U,0U,0U},{657U,0U,0U},{624U,0U,0U},{~0U,1549U,1556U},{~0U,1550U,1551U},{313U,0U,0U},{~0U,1552U,1555U},
	{~0U,1553U,1554U},{125U,0U,0U},{837U,0U,0U},{704U,0U,0U},{232U,0U,0U},{~0U,1558U,1605U},{~0U,1559U,1578U},{~0U,1560U,1561U},
	{250U,0U,0U},{~0U,1562U,1563U},{274U,0U,0U},{~0U,1564U,1575U},{~0U,1565U,1570U},{~0U,1566U,1569U},{~0U,1567U,1568U},{123U,0U,0U},
	{839U,0U,0U},{702U,0U,0U},{~0U,1571U,1574U},{~0U,1572U,1573U},{835U,0U,0U},{361U,0U,0U},{159U,0U,0U},{~0U,1576U,1577U},
	{195U,0U,0U},{658U,0U,0U},{~0U,1579U,1604U},{~0U,1580U,1603U},{~0U,1581U,1602U},{~0U,1582U,1589U},{~0U,1583U,1588U},{~0U,1584U,1587U},
	{~0U,1585U,1586U},{914U,0U,0U},{912U,0U,0U},{840U,0U,0U},{705U,0U,0U},{~0U,1590U,1599U},{~0U,1591U,1592U},{842U,0U,0U},
	{~0U,1593U,1598U},{~0U,1594U,1595U},{405U,0U,0U},{~0U,1596U,1597U},{15U,0U,0U},{439U,0U,0U},{85U,0U,0U},{~0U,1600U,1601U},
	{843U,0U,0U},{362U,0U,0U},{231U,0U,0U},{599U,0U,0U},{577U,0U,0U},{541U,0U,0U},{~0U,1607U,1788U},{~0U,1608U,1739U},
	{~0U,1609U,1610U},{254U,0U,0U},{~0U,1611U,1612U},{527U,0U,0U},{~0U,1613U,1658U},{~0U,1614U,1657U},{~0U,1615U,1620U},{~0U,1616U,1619U},
	{~0U,1617U,1618U},{625U,0U,0U},{290U,0U,0U},{245U,0U,0U},{~0U,1621U,1646U},{~0U,1622U,1633U},{~0U,1623U,1624U},{314U,0U,0U},
	{~0U,1625U,1626U},{706U,0U,0U},{~0U,1627U,1632U},{~0U,1628U,1629U},{86U,0U,0U},{~0U,1630U,1631U},{986U,0U,0U},{51U,0U,0U},
	{121U,0U,0U},{~0U,1634U,1645U},{~0U,1635U,1644U},{~0U,1636U,1637U},{844U,0U,0U},{~0U,1638U,1639U},{916U,0U,0U},{~0U,1640U,1643U},
	{~0U,1641U,1642U},{440U,0U,0U},{16U,0U,0U},{406U,0U,0U},{158U,0U,0U},{659U,0U,0U},{~0U,1647U,1648U},{626U,0U,0U},
	{~0U,1649U,1654U},{~0U,1650U,1651U},{707U,0U,0U},{~0U,1652U,1653U},{849U,0U,0U},{845U,0U,0U},{~0U,1655U,1656U},{335U,0U,0U},
	{708U,0U,0U},{558U,0U,0U},{~0U,1659U,1686U},{~0U,1660U,1685U},{~0U,1661U,1684U},{~0U,1662U,1683U},{~0U,1663U,1676U},{~0U,1664U,1669U},
	{~0U,1665U,1666U},{122U,0U,0U},{~0U,1667U,1668U},{917U,0U,0U},{84U,0U,0U},{~0U,1670U,1671U},{851U,0U,0U},{~0U,1672U,1673U},
	{387U,0U,0U},{~0U,1674U,1675U},{988U,0U,0U},{989U,0U,0U},{~0U,1677U,1678U},{336U,0U,0U},{~0U,1679U,1682U},{~0U,1680U,1681U},
	{386U,0U,0U},{388U,0U,0U},{850U,0U,0U},{291U,0U,0U},{600U,0U,0U},{578U,0U,0U},{~0U,1687U,1732U},{~0U,1688U,1705U},
	{~0U,1689U,1696U},{~0U,1690U,1695U},{~0U,1691U,1692U},{709U,0U,0U},{~0U,1693U,1694U},{363U,0U,0U},{847U,0U,0U},{315U,0U,0U},
	{~0U,1697U,1698U},{660U,0U,0U},{~0U,1699U,1704U},{~0U,1700U,1703U},{~0U,1701U,1702U},{918U,0U,0U},{390U,0U,0U},{848U,0U,0U},
	{710U,0U,0U},{~0U,1706U,1731U},{~0U,1707U,1730U},{~0U,1708U,1709U},{711U,0U,0U},{~0U,1710U,1711U},{120U,0U,0U},{~0U,1712U,1727U},
	{~0U,1713U,1726U},{~0U,1714U,1719U},{~0U,1715U,1718U},{~0U,1716U,1717U},{475U,0U,0U},{485U,0U,0U},{460U,0U,0U},{~0U,1720U,1725U},
	{~0U,1721U,1724U},{~0U,1722U,1723U},{507U,0U,0U},{508U,0U,0U},{489U,0U,0U},{456U,0U,0U},{991U,0U,0U},{~0U,1728U,1729U},
	{994U,0U,0U},{993U,0U,0U},{661U,0U,0U},{230U,0U,0U},{~0U,1733U,1738U},{~0U,1734U,1737U},{~0U,1735U,1736U},{194U,0U,0U},
	{193U,0U,0U},{627U,0U,0U},{275U,0U,0U},{~0U,1740U,1741U},{259U,0U,0U},{~0U,1742U,1787U},{~0U,1743U,1744U},{542U,0U,0U},
	{~0U,1745U,1746U},{559U,0U,0U},{~0U,1747U,1768U},{~0U,1748U,1767U},{~0U,1749U,1758U},{~0U,1750U,1755U},{~0U,1751U,1754U},{~0U,1752U,1753U},
	{119U,0U,0U},{118U,0U,0U},{337U,0U,0U},{~0U,1756U,1757U},{338U,0U,0U},{157U,0U,0U},{~0U,1759U,1766U},{~0U,1760U,1765U},
	{~0U,1761U,1764U},{~0U,1762U,1763U},{83U,0U,0U},{389U,0U,0U},{853U,0U,0U},{712U,0U,0U},{662U,0U,0U},{601U,0U,0U},
	{~0U,1769U,1772U},{~0U,1770U,1771U},{229U,0U,0U},{292U,0U,0U},{~0U,1773U,1774U},{628U,0U,0U},{~0U,1775U,1786U},{~0U,1776U,1785U},
	{~0U,1777U,1778U},{846U,0U,0U},{~0U,1779U,1784U},{~0U,1780U,1781U},{50U,0U,0U},{~0U,1782U,1783U},{441U,0U,0U},{13U,0U,0U},
	{391U,0U,0U},{713U,0U,0U},{192U,0U,0U},{528U,0U,0U},{~0U,1789U,1934U},{~0U,1790U,1933U},{~0U,1791U,1842U},{~0U,1792U,1841U},
	{~0U,1793U,1796U},{~0U,1794U,1795U},{267U,0U,0U},{579U,0U,0U},{~0U,1797U,1830U},{~0U,1798U,1829U},{~0U,1799U,1810U},{~0U,1800U,1801U},
	{316U,0U,0U},{~0U,1802U,1809U},{~0U,1803U,1808U},{~0U,1804U,1807U},{~0U,1805U,1806U},{407U,0U,0U},{990U,0U,0U},{920U,0U,0U},
	{855U,0U,0U},{714U,0U,0U},{~0U,1811U,1828U},{~0U,1812U,1827U},{~0U,1813U,1814U},{117U,0U,0U},{~0U,1815U,1818U},{~0U,1816U,1817U},
	{408U,0U,0U},{49U,0U,0U},{~0U,1819U,1826U},{~0U,1820U,1825U},{~0U,1821U,1824U},{~0U,1822U,1823U},{481U,0U,0U},{490U,0U,0U},
	{461U,0U,0U},{11U,0U,0U},{996U,0U,0U},{156U,0U,0U},{663U,0U,0U},{602U,0U,0U},{~0U,1831U,1832U},{244U,0U,0U},
	{~0U,1833U,1840U},{~0U,1834U,1839U},{~0U,1835U,1838U},{~0U,1836U,1837U},{116U,0U,0U},{852U,0U,0U},{715U,0U,0U},{664U,0U,0U},
	{228U,0U,0U},{543U,0U,0U},{~0U,1843U,1872U},{~0U,1844U,1845U},{560U,0U,0U},{~0U,1846U,1871U},{~0U,1847U,1870U},{~0U,1848U,1849U},
	{629U,0U,0U},{~0U,1850U,1867U},{~0U,1851U,1856U},{~0U,1852U,1853U},{115U,0U,0U},{~0U,1854U,1855U},{921U,0U,0U},{919U,0U,0U},
	{~0U,1857U,1858U},{364U,0U,0U},{~0U,1859U,1860U},{81U,0U,0U},{~0U,1861U,1862U},{48U,0U,0U},{~0U,1863U,1864U},{14U,0U,0U},
	{~0U,1865U,1866U},{459U,0U,0U},{457U,0U,0U},{~0U,1868U,1869U},{155U,0U,0U},{716U,0U,0U},{276U,0U,0U},{580U,0U,0U},
	{~0U,1873U,1932U},{~0U,1874U,1905U},{~0U,1875U,1886U},{~0U,1876U,1885U},{~0U,1877U,1884U},{~0U,1878U,1883U},{~0U,1879U,1880U},{365U,0U,0U},
	{~0U,1881U,1882U},{922U,0U,0U},{82U,0U,0U},{154U,0U,0U},{191U,0U,0U},{293U,0U,0U},{~0U,1887U,1888U},{227U,0U,0U},
	{~0U,1889U,1902U},{~0U,1890U,1893U},{~0U,1891U,1892U},{366U,0U,0U},{857U,0U,0U},{~0U,1894U,1895U},{854U,0U,0U},{~0U,1896U,1897U},
	{924U,0U,0U},{~0U,1898U,1901U},{~0U,1899U,1900U},{9U,0U,0U},{445U,0U,0U},{47U,0U,0U},{~0U,1903U,1904U},{339U,0U,0U},
	{717U,0U,0U},{~0U,1906U,1907U},{603U,0U,0U},{~0U,1908U,1909U},{630U,0U,0U},{~0U,1910U,1911U},{317U,0U,0U},{~0U,1912U,1923U},
	{~0U,1913U,1922U},{~0U,1914U,1919U},{~0U,1915U,1918U},{~0U,1916U,1917U},{442U,0U,0U},{443U,0U,0U},{995U,0U,0U},{~0U,1920U,1921U},
	{409U,0U,0U},{46U,0U,0U},{856U,0U,0U},{~0U,1924U,1931U},{~0U,1925U,1926U},{928U,0U,0U},{~0U,1927U,1928U},{992U,0U,0U},
	{~0U,1929U,1930U},{12U,0U,0U},{8U,0U,0U},{860U,0U,0U},{561U,0U,0U},{519U,0U,0U},{~0U,1935U,2004U},{~0U,1936U,1937U},
	{529U,0U,0U},{~0U,1938U,1939U},{544U,0U,0U},{~0U,1940U,1965U},{~0U,1941U,1964U},{~0U,1942U,1961U},{~0U,1943U,1946U},{~0U,1944U,1945U},
	{190U,0U,0U},{665U,0U,0U},{~0U,1947U,1954U},{~0U,1948U,1949U},{153U,0U,0U},{~0U,1950U,1953U},{~0U,1951U,1952U},{926U,0U,0U},
	{393U,0U,0U},{859U,0U,0U},{~0U,1955U,1956U},{340U,0U,0U},{~0U,1957U,1958U},{367U,0U,0U},{~0U,1959U,1960U},{923U,0U,0U},
	{925U,0U,0U},{~0U,1962U,1963U},{294U,0U,0U},{631U,0U,0U},{581U,0U,0U},{~0U,1966U,1981U},{~0U,1967U,1968U},{604U,0U,0U},
	{~0U,1969U,1980U},{~0U,1970U,1973U},{~0U,1971U,1972U},{719U,0U,0U},{151U,0U,0U},{~0U,1974U,1979U},{~0U,1975U,1978U},{~0U,1976U,1977U},
	{80U,0U,0U},{927U,0U,0U},{858U,0U,0U},{720U,0U,0U},{226U,0U,0U},{~0U,1982U,2003U},{~0U,1983U,2000U},{~0U,1984U,1985U},
	{666U,0U,0U},{~0U,1986U,1987U},{152U,0U,0U},{~0U,1988U,1989U},{114U,0U,0U},{~0U,1990U,1999U},{~0U,1991U,1992U},{410U,0U,0U},
	{~0U,1993U,1998U},{~0U,1994U,1997U},{~0U,1995U,1996U},{492U,0U,0U},{484U,0U,0U},{458U,0U,0U},{10U,0U,0U},{392U,0U,0U},
	{~0U,2001U,2002U},{667U,0U,0U},{318U,0U,0U},{243U,0U,0U},{~0U,2005U,2006U},{530U,0U,0U},{~0U,2007U,2050U},{~0U,2008U,2009U},
	{562U,0U,0U},{~0U,2010U,2021U},{~0U,2011U,2020U},{~0U,2012U,2013U},{225U,0U,0U},{~0U,2014U,2019U},{~0U,2015U,2016U},{718U,0U,0U},
	{~0U,2017U,2018U},{368U,0U,0U},{862U,0U,0U},{189U,0U,0U},{277U,0U,0U},{~0U,2022U,2049U},{~0U,2023U,2024U},{295U,0U,0U},
	{~0U,2025U,2046U},{~0U,2026U,2027U},{723U,0U,0U},{~0U,2028U,2029U},{863U,0U,0U},{~0U,2030U,2031U},{929U,0U,0U},{~0U,2032U,2045U},
	{~0U,2033U,2044U},{~0U,2034U,2037U},{~0U,2035U,2036U},{487U,0U,0U},{493U,0U,0U},{~0U,2038U,2043U},{~0U,2039U,2040U},{509U,0U,0U},
	{~0U,2041U,2042U},{512U,0U,0U},{256U,0U,0U},{483U,0U,0U},{444U,0U,0U},{45U,0U,0U},{~0U,2047U,2048U},{722U,0U,0U},
	{150U,0U,0U},{605U,0U,0U},{545U,0U,0U}
	};

}

/***************************************
Methods of class InterFrameDecompressor:
***************************************/

InterFrameDecompressor::InterFrameDecompressor(IO::File& sFile)
	:file(&sFile),
	decoder(sFile,interFrameDecompressorTree)
	{
	}

void InterFrameDecompressor::decompressFrame(unsigned int width,unsigned int height,const Pixel* pixels0,Pixel* pixels1)
	{
	/* Decode all pixel differences: */
	const Pixel* p0Ptr=pixels0;
	Pixel* p1Ptr=pixels1;
	Pixel* p1End=pixels1+(height*width);
	while(p1Ptr!=p1End)
		{
		/* Decode the next code: */
		unsigned int code=decoder.decode();
		
		/* Check for a zero run: */
		if(code>outOfRange)
			{
			/* Calculate the end of the zero run: */
			Pixel* zeroEnd=p1Ptr+(code-outOfRange);
			
			/* Check for overrun errors, which can't happen in a correct code stream: */
			if(zeroEnd>p1End)
				throw std::runtime_error("InterFrameDecompressor::decompressFrame: Invalid zero run");
			
			/* Copy a run of pixels from the previous frame: */
			for(;p1Ptr!=zeroEnd;++p0Ptr,++p1Ptr)
				*p1Ptr=*p0Ptr;
			}
		else if(code<outOfRange)
			{
			/* Apply the decoded delta: */
			*p1Ptr=*p0Ptr+Pixel(code-codeMax);
			
			++p0Ptr;
			++p1Ptr;
			}
		else
			{
			/* Read the unencoded out-of-range delta: */
			*p1Ptr=*p0Ptr+Pixel(decoder.readBits(sizeof(Pixel)*8U));
			
			++p0Ptr;
			++p1Ptr;
			}
		}
	
	/* Flush the decoder: */
	decoder.flush();
	}